第33章：堆排序进阶

挑战1：为数组添加堆排序

给数组添加一个 heapSort() 方法。这个方法应该按升序对数组进行排序。启动模板在启动程序的playground上。

挑战2：理论

当按升序执行堆排序时，这些起始数组中哪一个需要的比较最少？

• [1,2,3,4,5]

• [5,4,3,2,1]

挑战3：降序

第32章中堆排序的当前实现是按升序排序的。你将如何进行降序排序？

解决方案

挑战1的解决方案

要给数组添加堆排序，必须创建一个扩展，其中数组中的元素必须是可比较的。其他都很简单，因为实现方式与第32章中的堆类似。

你现在引用的是数组的内部属性。

挑战2的解决方案

使用堆排序对元素进行升序排序时，你首先需要一个最大堆。你需要看的是构建最大堆时发生的比较次数。

[5,4,3,2,1]将产生最少的比较次数，因为它已经是一个最大堆了，而且没有发生交换的情况。

当建立一个最大堆时，你只看父节点。在这个例子中，有两个父节点有两个比较。

[1,2,3,4,5]将产生最多的比较次数。有两个父节点，但你必须进行三次比较。

挑战3的解决方案

只需在排序前使用最小堆而不是最大堆。

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

---

上一章	目录	下一章