第35章：快速排序进阶

这里有几个快速排序的挑战，以确保你能掌握这个题目。在看解决方案之前，请确保自己尝试一下。

挑战1：迭代快速排序

在本章中，你学到了如何递归地实现快速排序。这里的挑战是以迭代方式实现。请选择你在本章中学到的任何分区策略。

挑战2：合并排序或快速排序

解释何时以及为何使用合并排序而不是快速排序。

挑战 3：用 Swift 标准库进行分区库

使用 Swift 标准库中的 partition(by:) 函数实现 快速排序。

更多信息请参考苹果的文档：https://developer.apple.com/documentation/Swift/array/3017524-partition

解决方案

挑战1的解决方案

在第34章，你以递归方式实现了快速排序。让我们看看如何迭代实现。这个解决方案使用Lomuto的分区策略。

这个函数接收了一个数组和low和high之间的范围。你将利用堆栈来存储成对的开始和结束值。

让我们来看看解决方案。

1. 创建一个存储索引的堆栈。

2. 将起始的低点和高点边界推到堆栈上以启动算法。

3. 只要堆栈不是空的，快速排序就没有完成。

4. 从堆栈中获得一对开始和结束的索引。

5. 用当前的开始和结束索引执行Lomuto的分区。回顾一下，Lomuto挑选最后一个元素作为支点，并将分区分成三部分：小于支点的元素，支点，最后是大于支点的元素。

6. 分割完成后，检查并添加下界的开始和结束索引，以便以后分割下半部分。

7. 同样地，检查并添加上界的开始和结束指数，以便以后对上半部分进行分区。

你用堆栈来存储一对开始和结束的索引来执行分区。让我们检查一下，看看你的迭代版quicksort是否有效。

var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortIterativeLomuto(&list, low: 0, high: list.count - 1) 
print(list)

挑战2的解决方案

• 当你需要稳定性时，合并排序比Quicksort更合适。合并排序很稳定，并保证O(n log n)。而快速排序则没有这些特点，它不稳定，性能可能差到O(n²)。

• 合并排序对于较大的数据结构或元素分散在整个内存中的数据结构来说效果更好。当元素被存储在一个连续的块中时，快速排序的工作效果最好。

挑战3的解决方案

要在一个集合上执行快速排序，必须具备以下条件。

• 集合必须是MutableCollection。这使你有能力改变集合中的元素的值。

• 集合必须是一个双向的集合。这给了你向前和向后遍历集合的能力。快速排序依赖于一个集合的第一个和最后一个索引。

• 集合中的元素必须是可比较的。首先，添加以下扩展。

这里你定义了一个叫做quicksort()的函数。这个函数在内部调用了一个quicksortLumuto(_:)，它接收了low和high的索引来启动排序算法。

接下来在quicksortLumuto(_:)中添加以下内容。

1. 继续在集合上执行快速排序，直到开始和结束索引相互重叠。

2. Lumuto的分区总是取集合中的最后一个元素来执行分区。

3. 对集合中的元素进行分割，并返回满足元素大于pivotValue的条件的第一个索引p。索引p之前的元素代表不满足谓词的元素，而p之后的元素代表满足条件的元素。

4. 处理基本情况。如果p是最后一个索引，则移动到之前的索引。考虑下面这种情况。

如果p是最后一个索引，而你进行了分区，那么分区仍然是一样的!

记住，p之前的元素并不满足分区。你会进入一个递归循环，直到你的内存用完为止! 你在第5步中执行的第一个分区将拥有与前一个分区相同的元素数量。

5. 在第一个分区上执行Quicksort，该分区由不大于pivotValue的元素组成。

6. 在由大于pivotValue的元素组成的第二个分区上执行快速排序。

为了测试它，添加以下内容。

var numbers = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
print(numbers) 
numbers.quicksort() 
print(numbers)

有趣的是：如果你看一下partition(by:)的实现，你会发现_partitionImpl(by:)采用了与Hoare的分区类似的策略。请看这里：http://bit.ly/partitionimpl

---

上一章	目录	下一章