堆排序

Author Avatar
Brian Lee 8月 15, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:堆排序


原理

  • 使用一个面向最大元素的优先队列并重复删除最大元素
  • 分为两个阶段:堆的构造阶段下沉排序阶段

复杂度

时间复杂度

$O(NlogN)$

空间复杂度

$O(1)$


堆的构造

目的

将原始数组重新组织安排进一个堆中

实现

  • 可以从左到右遍历数组,将各元素插入堆中,每次插入后用swim()保证堆有序。时间复杂度为 $O(NlogN)$
  • 另一种更高效的方法是从右至左用sink()构造子堆。如果一个结点的两个子结点都已经是堆了,那么在该结点上调用sink()可以将它们变成一个堆。这个过程会递归地建立起堆。时间复杂度为 $O(N)$ 。在此我们采用这种方法。

图示

构造堆

构造堆


下沉排序

目的

从堆中按递减顺序取出所有元素并得到排序结果

实现

将堆中的最大元素删除,然后放入堆缩小数组后空出的位置

时间复杂度为 $NlogN$

图示

下沉排序


代码

public static void sort(Comparable[] a) {
        int N = a.length - 1;
        //构造堆
        for (int k = N / 2; k >= 1; k--)
            sink(a, k, N);
        //下沉排序
        while (N > 1) {
            exch(a, 1, N--);
            sink(a, 1, N);
        }
    }
    private static void sink(Comparable[] a, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(a, j, j + 1))
                j++;
            if (!less(a, k, j))
                break;
            exch(a, k, j);
            k = j;
        }

排序过程

堆排序过程


优缺点

优点

  • 是唯一能够同时最优地利用空间和时间的方法
  • 对记录数较大的文件很有效

缺点

  • 无法利用缓存。数组元素很少和相邻的其他元素进行比较,因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法

源代码

https://github.com/XutongLi/Algorithm-Learn/blob/master/src/S2_Sorting/S2_4_5_HeapSort/HeapSort.java


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/08/15/heapSort/