首页 > 代码库 > 普林斯顿公开课 算法4-3:堆排

普林斯顿公开课 算法4-3:堆排

堆排的灵感源自于堆的数据结构。它是一种原地排序算法,不需要额外的临时数组。


基本思想


堆排的基本思想是:

  1. 先建立一个最大堆

  2. 将最大的元素移动到数组末尾,减小堆的大小,调整最大堆使其符合最大堆的性质

  3. 重复第二步,直到最大堆耗尽为止


第一个步骤建立最大堆的代码非常简单,只要对每个节点执行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]);
    }
}