学步园

package ch10;

public class HeapSort {
	/**
	 * 筛选算法，即一次堆调整，调整为大顶堆
	 * 此算法假设t[s...m]除了t[s]外已经是一个大顶堆
	 * @param <T>
	 * @param t 
	 * @param s
	 * @param m
	 * @return true:成功进行一次筛选，false：筛选出错
	 */
	private static <T extends Comparable> boolean heapAdjust(T[] t, int s, int m){
		if(t==null || t.length==1) return true;
		
		T temp = t[s];
		for(int j = 2*s+1 ; j<=m ; j = 2*j+1){
			if(j+1<=m && t[j+1].compareTo(t[j]) > 0) j++;
			if(temp.compareTo(t[j]) >= 0) break;//这个时候之所以能结束循环，是因为我们假设此算法是在t[s...m]除t[s]外已经是大顶堆的情况下进行的
			t[s] = t[j];
			s = j;//s是temp应该插入的位置			
		}
		t[s] = temp;
		
		return true;
	}
	
	/**
	 * 堆排序，用大顶堆进行排序，最终得到的是升序数组
	 * @param <T>
	 * @param t
	 * @return
	 */
	public static <T extends Comparable> boolean heapSort(T[] t){
		if(t==null || t.length<=1) return true;
		
		for(int i = t.length/2 - 1; i>=0; i--){//此循环用于调整原始的数组使其成为大顶堆
			heapAdjust(t, i, t.length-1);
		}
		
		for(int j = t.length-1; j>0 ;j--){//每次选取对顶元素和最后一个元素交换，然后调整堆，再选取最大元素，直至有序
			T temp = t[j];
			t[j] = t[0];
			t[0] = temp;
			heapAdjust(t, 0 ,j-1);
		}
		
		return true;
	}
	
	public static void main(String[] args) {
		Integer[] arr = new Integer[]{2,6,4,1,4,3,2,1,6,4,4,8};
		HeapSort.<Integer>heapSort(arr);
		for(int i : arr){
			System.out.println(i);
		}
	}
	
}