第32章：堆排序

Heapsort是另一种基于比较的算法，它使用堆对数组进行升序排序。本章建立在第22章 "堆 "中介绍的堆概念之上。

Heapsort利用了堆的优势，根据定义，堆是一个部分排序的二叉树，具有以下特点。

  1. 在一个最大堆中，所有的父节点都比它们的子节点大。

  2. 在最小堆中，所有父节点都比子节点小。下图显示了一个父节点值下划线的堆。

开始工作

打开启动器playground。这个playground已经包含了一个最大堆的实现。你的目标是扩展Heap，使其也能进行排序。在你开始之前，让我们看一个堆排序工作的视觉例子。

例子

对于任何给定的未经排序的数组，要从低到高排序，堆排序必须首先将这个数组转换为最大堆。

这个转换是通过筛选所有的父节点来完成的，最终在正确的位置。得到的最大堆是。

这与以下数组相对应。

因为单个筛下操作的时间复杂度是O(log n)，所以建立一个堆的总时间复杂度是O(n log n)。

让我们来看看如何对这个数组进行升序排序。

因为最大堆中最大的元素总是在根部，所以你开始将索引0的第一个元素与索引n-1的最后一个元素进行交换。因此，下一步是将新的根音符5向下筛选，直到它落在正确的位置。

注意，你排除了堆的最后一个元素，因为你不再认为它是堆的一部分，而是排序的数组的一部分。

作为筛选5的结果，第二大元素21成为新的根。现在你可以重复之前的步骤，将21与最后一个元素6交换，缩小堆并向下筛选6。

你开始看到一个模式了吗？堆排序是非常简单明了的。当你交换第一个和最后一个元素时，较大的元素会以正确的顺序移到数组的后面。你重复交换和筛选的步骤，直到你达到一个大小为1的堆。

然后，该数组被完全排序。

注意：这个排序过程与第26章的选择排序非常相似。

实现

接下来，你要实现这个排序算法。实际的实现非常简单，因为沉重的工作已经由siftDown方法完成。

下面是发生的事情。

  1. 你首先制作一个堆的副本。在heap sort对elements数组进行排序后，它就不再是一个有效的heap了。通过在堆的副本上工作，你可以确保堆保持有效。

  2. 你循环浏览数组，从最后一个元素开始。

  3. 将第一个元素和最后一个元素交换。这个交换将最大的未排序的元素移到它的正确位置。

  4. 因为现在的堆是无效的，你必须从新的根节点开始筛选。结果是，下一个最大的元素将成为新的根节点。

注意：为了支持堆排序，你已经在siftDown方法中加入了upTo参数。这样一来，向下筛选只使用数组中未排序的部分，而数组会随着每次循环迭代而缩小。

最后，让你的新方法试一试。

let heap = Heap(sort: >, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5]) 
print(heap.sorted())

这段代码应该打印如下。

[2, 5, 6, 8, 9, 12, 18, 21, 26]

性能

尽管你从内存排序中获益，但堆排序的性能在最好、最差和平均情况下都是O(n log n)。这种性能的统一性是因为你必须对整个列表进行一次遍历，而且，每次交换元素时，你必须进行一次筛选，这是一个O（log n）的操作。

堆排序也不是一个稳定的排序，因为它取决于元素是如何布置和放入堆的。例如，如果你按等级对一副牌进行堆排序，你可能会看到它们的套牌与原来的牌相比，顺序发生了变化。

关键点

  1. 交换第一个和最后一个元素。

  2. 从根部开始进行筛选，以满足作为一个堆的要求。

  3. 将数组的大小减少一个，因为最后的元素将是最大的元素。

  4. 重复这些步骤，直到你到达数组的起点。

上一章 目录 下一章