堆的原理与实现以及排序

 代码实现：

public class HeapSort {
	private static boolean less(Comparable[] head,int i,int j) {
		return head[i].compareTo(head[j])<0;
	}
	private static void exch(Comparable[] head,int i,int j) {
		Comparable tmp=head[i];
		head[i]=head[j];
		head[j]=tmp;
	}
	//根据原数组source，构造出堆heap
	private static void createHeap(Comparable[] source,Comparable[] head) {
		//1.把source中的数据拷贝到heap中，从heap的1索引处开始填充
		System.arraycopy(source, 0, head, 1, source.length);
		//2.从heap索引的一半处开始倒叙遍历，对得到的每一个元素做下沉操作
		for(int i=head.length/2;i>0;i--) {
			sink(head,i,head.length-1);
		}
	}
	//对source数组中的数据从小到大排序
	public static void sort(Comparable[] source) {
		//1.创建一个比原数组大1的数组
		Comparable[] head=new Comparable[source.length+1];
		//2.构造堆
		createHeap(source,head);
		//3.堆排序
		//3.1定义一个变量，记录heap中未排序的所有元素中最大的索引
		int N=head.length-1;
		
		while(N!=1) {
			//3.2交换heap中索引1处的元素和N处的元素
			exch(head,1,N);
			N--;
			//3.3对索引1处的元素在0~N范围内做下沉操作
			sink(head,1,N);
		}
		//4.heap中的数据已经有序，拷贝到source中
		System.arraycopy(head, 1, source, 0, source.length);
	}
	//在heap堆中，对target处的元素做下沉，范围是0~range
	private static void sink(Comparable[] head,int target,int range) {
		while(2*target<=range) {
			int max;
			if(2*target+1<=range) {
				if(less(head,2*target,2*target+1)) {
					max=2*target+1;
				}else {
					max=2*target;
				}
			}else {
				max=2*target;
			}
			if(!less(head,target,max)) {
				break;
			}
			exch(head,target,max);
			target=max;
		}
	}
}