【译】Swift算法俱乐部-堆排序

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。

?andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习?。当然也欢迎加⭐️，?????。

本文的翻译原文和代码可以查看?swift-algorithm-club-cn/Heap Sort

---

堆排序(Heap Sort)

使用堆将数组从低到高排序。( 译注： 也可以从高到低排序)

堆是一个部分排序的二叉树，存储在数组中。 堆排序算法利用堆的结构来执行快速排序。

要从最低到最高排序，堆排序首先将未排序的数组转换为max-heap，让数组中的第一个元素是最大的。

假设，需要排序的数组为：

[ 5, 13, 2, 25, 7, 17, 20, 8, 4 ]
复制代码

首先变成了一个如下所示的max-heap：

这个堆的数组是：

[ 25, 13, 20, 8, 7, 17, 2, 5, 4 ]
复制代码

这几乎不是想要的从低到高排序！

现在开始排序：我们将第一个元素（索引0）与索引n-1的最后一个元素交换，得到：

[ 4, 13, 20, 8, 7, 17, 2, 5, 25 ]
  *                          *
复制代码

现在新的根节点4小于其子节点，因此我们使用shift down或“堆化(heapify)”将0到n-2元素修复成max-heap。 修复堆后，新的根节点现在是数组中的第二大项：

[20, 13, 17, 8, 7, 4, 2, 5 | 25]
复制代码

重要提示：当我们修复堆时，我们忽略索引为n-1的最后一项。 最后一项是数组中的最大值，因此它已经在最终排序的位置了。 |栏表示数组的已排序部分的开始位置。 从现在开始，我们将单独除了数组余下的部分（|前面的部分）。

同样，我们将第一个元素与最后一个元素交换（这次是在索引n-2）：

[5, 13, 17, 8, 7, 4, 2, 20 | 25]
 *                      *
复制代码

并修复堆以使其再次成为有效的max-heap：

[17, 13, 5, 8, 7, 4, 2 | 20, 25]
复制代码

正如您所看到的，最大项正在向后移动。 我们重复这个过程，直到到达根节点，也就对整个数组进行了排序。

注意： 此过程与选择排序 非常相似，它重复查找数组其余部分中的最小项。 提取最小值或最大值是堆擅长做的。

堆排序的性能最佳，最差和平均情况下都是O(n lg n)。 因为我们直接修改数组，所以可以就地执行堆排序。 但它不是一个稳定的类型：不保留相同元素的相对顺序。

以下是在Swift中实现堆排序的方法：

extension Heap {
  public mutating func sort() -> [T] {
    for i in stride(from: (elements.count - 1), through: 1, by: -1) {
      swap(&elements[0], &elements[i])
      shiftDown(0, heapSize: i)
    }
    return elements
  }
}
复制代码

为堆实现添加了一个sort()函数。 这个函数的使用方式：

var h1 = Heap(array: [5, 13, 2, 25, 7, 17, 20, 8, 4], sort: >)
let a1 = h1.sort()
复制代码

因为我们需要一个max-heap来从低到高排序，你需要给Heap提供sort函数的反向排序。 要对<进行排序，必须使用>作为sort函数创建Heap对象。 换句话说，从低到高的排序会创建一个max-heap并将其转换为min-heap（ 译注： 这边的意思就是排完序以后就变成了一个从小到大的特殊的min-heap）。

我们可以为此编写一个方便的辅助函数：

public func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T] {
  let reverseOrder = { i1, i2 in sort(i2, i1) }
  var h = Heap(array: a, sort: reverseOrder)
  return h.sort()
}
复制代码

使用方式：

let a2 = heapsort([5, 13, 2, 25, 7, 17, 20, 8, 4], <)
print(a2)
复制代码

作者： Matthijs Hollemans
翻译：Andy Ron
校对：Andy Ron