堆排序

堆排序

• • 堆排序

用堆来实现一种经典而优雅的排序算法——堆排序

堆排序可以分为两个阶段：
1、堆的构造阶段：将原始数组重新组织安排进一个最大堆中，使其堆有序
2、下沉排序阶段：从堆中按递减顺序取出所有元素并得到排序结果

如下图，以对S O R T E X A M P L E 排序为例：
首先本地构造一个最大堆，即对节点进行 Sink() 操作，使其符合二叉堆的性质。
然后再重复删除根节点，也就是最大的元素，操作方法与之前的二叉堆的删除元素类似。

一 创建最大二叉堆

任意顺序 -> 堆有序
由N个给定的元素构造一个堆：
方法1：从左至右遍历数组，用 swim() 保证扫描指针左侧的所有元素已经是一棵堆有序的完全树，就像连续向优先队列中插入元素一样。

方法2(更高效)：从右至左用 sink() 构造子堆。数组的每个位置都已经是一个子堆的根节点了，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用 sink() 可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。

//创建最大二叉堆
for (int k = N / 2; k >= 1; k--) {   //开始时只需扫描数组中的一半元素，因为可以跳过大小为1的子堆
     Sink(a, k, N);
}

二 下沉排序

堆有序 -> 已排序
堆排序的主要工作都是在第二阶段完成的。
循环将最大的元素 a[1] 和 a[N] 交换，N–，然后在位置1上调用 sink() 方法修复堆，直至堆变空。

//循环移除顶部元素到数组末尾，然后利用sink()重建堆
while (N > 1){
      Swap(a, 1, N--);
      Sink(a, 1, N);
}

三 性能分析

在将 N$N$ 个元素排序时，堆排序最多需要 2NlgN+2N$2NlgN+2N$ 次比较和 NlgN+N$NlgN+N$ 次交换

2N$2N$ 项来自于堆的构造，2NlgN$2NlgN$ 来自于每次下沉操作最大可能需要 2lgN$2lgN$ 次比较

四 算法特点

优点：堆排序是唯一能够同时最优地利用空间和时间的方法。它是就地排序，并且最坏情况下它也能保证时间复杂度为 O(NlogN)$O(NlogN)$ 。经典的合并排序不是就地排序，它需要线性长度的额外空间；快速排序虽然是就地排序，但其最坏时间复杂度为 N2$N^2$

缺点：堆排序对时间和空间都进行了优化，但是：

1. 其内部循环要比快速排序要长。
2. 其对元素的操作通常在N和N/2之间进行比较和交换，所以对于大的序列来说，两个操作数之间间隔比较远，对CPU缓存利用效率低。缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快排、归并排序、甚至是希尔排序。
3. 非稳定性排序。