堆排的灵感源自于堆的数据结构。它是一种原地排序算法,不需要额外的临时数组。
堆排的基本思想是:
先建立一个最大堆
将最大的元素移动到数组末尾,减小堆的大小,调整最大堆使其符合最大堆的性质
重复第二步,直到最大堆耗尽为止
第一个步骤建立最大堆的代码非常简单,只要对每个节点执行sink操作即可。
1
2
|
for ( int k
= N/ 2 ;
k >= 1 ;
k--) sink(a,
k, N); |
第二个步骤也很简单,代码如下:
1
2
3
4
|
while (N
> 1 )
{ exch(a, 1 ,
N--); sink(a, 1 ,
N); } |
下图是堆排算法的动画:
http://www.sorting-algorithms.com/animation/50/random-initial-order/heap-sort.gif
堆排在构建堆的过程中需要2N次比较和交换。
在排序的过程中需要NlgN次比较和交换。
堆排是一种最坏情况下复杂度为NlogN的原地排序算法,这两种特性是归并排序和快排都做不到的。
堆排不是一种稳定的排序算法。不能很好的利用CPU缓存,因此性能一般。
下图展示了排序算法与算法特性之间的关系
public class HeapSort { public static void sort(Comparable[] a) { // 需要假想数组a是从1开始编号的 int N = a.length; // 建立最大堆 for(int i=N/2;i>=1;i--){ // 注意,从最底层开始建立,而不是从最顶层开始建立 sink(a, i, N); } // 依次取出最大元素,放在末尾 while(N > 1) { exch(a, 1, N); N--; sink(a, 1, N); } } public static void sink(Comparable[] a, int k, int N) { // 循环直到没有子节点为止 while(k*2 <= N) { int parent = k; int child1 = k*2; int child2 = child1+1; // 如果父亲比任意一个子节点要小 if(less(a,parent,child1,N) || less(a,parent,child2,N)){ // 选出较大的子节点 int greater; if(less(a,child1,child2,N)) { greater = child2; } else { greater = child1; } // 将较大的节点与父节点交换 exch(a, greater, parent); // 为下次循环做准备 k = greater; } else { break; // 注意:不要忘记跳出循环 } } } public static void exch(Comparable[] a, int x, int y) { // 将以1为起点的数组转换成以0为起点的数组 x-=1;y-=1; SortUtil.exch(a, x,y); } public static boolean less(Comparable[] a, int x, int y, int N) { // 将以1为起点的数组转换成以0为起点的数组 x-=1;y-=1; // 将null值视为无穷小 if(x>=N) return true; if(y>=N) return false; return SortUtil.less(a[x],a[y]); } }
普林斯顿公开课 算法4-3:堆排,布布扣,bubuko.com
原文:http://blog.csdn.net/caipeichao2/article/details/29597585