排序----堆排序

上一篇：快速排序

数据结构--堆的构造和实现

堆排序可以分为两个阶段：

1. 构造堆。将原始数组重新组织安排进一个堆中
2. 下沉排序。从堆中按递减顺序取出所有元素并得到排序结果

用下沉操作由N个元素构造堆只需少于2N次比较以及少于N次交换。

将N个元素排序，堆排序只需少于（2NlgN+2N)次比较以及一半次数的交换。2N来字堆的构造。

堆排序的特点：

• 唯一的能够同时最优地利用空间和时间的方法。
• 无法利用缓存。数组元素很少和相邻的元素直接比较，因此缓存未命中的次数远远高于其他排序算法。
• 能够在插入操作和删除最大元素操作混合的动态场景中保证对数级别的运行时间。

堆排序实现要点：

• 代码中堆是用数组实现的，数组a0弃之不用，堆顶元素存在a1中。
• 最先构造的堆是最大堆（元素越大越靠近堆顶），然后通过循环交换a1和aN--元素，使大元素沉到数组底部，并修复堆。如此循环直到堆为空，则实现堆的数组中元素已经排好序了。
• 下面代码是堆排序主要算法，具体堆的实现可以参考数据结构----堆。

public static void sort(Comparable[] a){
	int N = a.length;
	for(int k=N/2;k>=1;k--)//构造堆
		sink(a,k,N);//由上至下的堆有序化（下沉）的实现
	while(N>1){
		exch(a,1,N--);//交换
		sink(a,1,N);//修复堆
	}
}

下一篇：排序算法总结