堆排序(HEAP SORT)

堆排序是简单选择排序的进化版本，也是使用了选择的思想。简单选择排序是每趟进行顺序遍历选择出最大(小)的元素。而堆排序是通过使用数据结构堆进行选择最大(小)的元素。这两个排序算法唯一的区别也只有这个地方。

下面先介绍数据结构堆的定义：

• 小顶堆 left { frac{k_{i}leqslant k_{2i+1}}{k_{i}leqslant k_{2i+2}}；
• 大顶堆 left { frac{k_{i}geqslant k_{2i+1}}{k_{i}geqslant k_{2i+2}}；
• 其中，i=0,1,…,left lfloor frac{n}{2} right rfloor。

堆排序的一般步骤(以小顶堆为例)：

• 从最后一个非终端结点left lfloor frac{n}{2} right rfloor开始遍历；
• 对于每一个遍历到的根结点，比较其左右孩子，选择出最小的结点值，与根结点交换值；
• 为了保证交换后堆的特性，堆子结点与根节点交换时，如果该子结点还有孩子结点，还要向下进行交换建堆；
• 堆建成后，删除根结点，用最后一个结点n代替(此操作与简单选择排序操作相似)；
• 继续执行这4步，直到排序完成。

堆的定义类似于完全二叉树，可以理解为完全二叉树所有非终端结点的值不大于(小于)其左、右孩子结点的值。依此规则建堆的话，我们遍历寻找最大(小)结点的步骤就得以简化，堆顶就是我们需要找的值。之前简单选择排序是逐个顺序比较，一趟遍历要执行(n-i+1)次，堆排序是从最后一个非终端结点left lfloor frac{n}{2} right rfloor开始建堆，所以只执行left lfloor frac{n-i+1}{2} right rfloor次。效率增强显而易见。

• 堆排序使用就地排序，只是删除结点时需要一个临时空间存储变量，其余操作不需要额外的空间，空间复杂度是O(n);
• 在建堆的比较过程中，从最后一个非空结点开始，所以最多是left lfloor log_{2}n right rfloor+1次，需要执行(n-1)次，所以时间复杂度是Oleft ( nlog n right )；
• 在建堆交换的过程中，只是子结点和双亲比较，所以不稳定。

堆排序实例(以小顶堆为例)：

• 初始序列为：{49,38,65,97,76,13,27,49}；
• 开始建堆，从left lfloor frac{n}{2} right rfloor开始，本例中是第四个结点97，和子结点49比较，子结点较小，进行交换；第三结点65，和子结点13和27进行比较，与较小的13进行交换；第二结点38，与子结点49和76比较，不需要交换；根结点49，与子结点38和13进行比较，与较小的13进行交换。此时第三个结点发生了变动，为了保证堆的特性，还要将该结点与子结点进行比较，使用较小的右子结点27与第三结点49进行交换。{13,38,27,49,76,65,49,97}；
• 删除根结点13，使用最后一个结点97代替；{97,38,27,49,76,65,49},13；
• 重复建堆，直到所有结点都已排序完成。下面只附上结果，不再复述重复的步骤； 调整堆：{27,38,49,49,76,65,97},13；
• 删除根结点：{97,38,49,49,76,65},27,13；
• 调整堆：{38,49,49,97,76,65},27,13；
• 删除根结点：{65,49,49,97,76},38,27,13；
• 调整堆：{49,65,49,97,76},38,27,13；
• 删除根结点：{76,65,49,97},49,38,27,13；
• 调整堆：{49,65,76,97},49,38,27,13；
• 删除根结点：{97,65,76},49,49,38,27,13；
• 调整堆：{65,97,76},49,49,38,27,13；
• 删除根结点：{76,97},65,49,49,38,27,13；
• 调整堆：{76,97},65,49,49,38,27,13；
• 删除根结点：97,76,65,49,49,38,27,13。排序结束，这样建立排序的结果是倒序的，建立小顶堆，结果是递减的序列，建立大顶堆，得到的递增的序列。

原文链接：堆排序(HEAP SORT)，转载请注明来源！