35.快速排序挑战¶

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

挑战1：快速排序迭代¶

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

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

解释一下什么时候以及为什么你会使用合并排序而不是快速排序。

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

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

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

解决方案¶

挑战1的解决方案¶

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

这个函数接收一个数组和low与high之间的范围。你将利用堆栈来存储成对的start和end值。

public func quicksortIterativeLomuto<T: Comparable>(_ a: inout [T],
                                                    low: Int,
                                                    high: Int) {
  var stack = Stack<Int>() // 1
  stack.push(low) // 2
  stack.push(high)

  while !stack.isEmpty { // 3
    // 4
    guard let end = stack.pop(),
          let start = stack.pop() else {
      continue
    }

    let p = partitionLomuto(&a, low: start, high: end) // 5

    // 6
    if (p - 1) > start {
      stack.push(start)
      stack.push(p - 1)
    }

    // 7
    if (p + 1) < end {
      stack.push(p + 1)
      stack.push(end)
    }
  }

}

让我们来看看解决方案：

创建一个存储索引的堆栈。
在堆栈上推送起始的low和high的边界，以启动该算法。
只要堆栈不是空的，快速排序就没有完成。
从堆栈中获得一对start和end的索引。
用当前的start和end索引执行Lomuto的分区。回顾一下，Lomuto选取最后一个元素作为支点，将分区分成三部分：小于支点的元素，支点，最后是大于支点的元素。
分割完成后，检查并添加下界的start和end索引，以便以后分割下半部分。
同样，检查并添加上界的start和end指数，以便以后对上半部分进行分区。

你用堆栈来存储一对start和end的索引来执行分区。

让我们检查一下你的迭代版快速排序是否有效：

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的解决方案¶

当你需要稳定性时，合并排序比快速排序更合适。合并排序很稳定，并保证O(n log n)。而快速排序则没有这些特点，它不稳定，性能可能差到O(n²)。
合并排序对于较大的数据结构或元素分散在整个内存中的数据结构来说效果更好。当元素被存储在一个连续的块中时，快速排序的效果最好。

挑战3的解决方案¶

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

集合必须是一个MutableCollection。这使你有能力改变集合中的元素的值。
集合必须是一个BidirectionalCollection。这给了你向前和向后遍历集合的能力。快速排序依赖于一个集合的第一个和最后一个索引。
集合中的元素必须是Comparable的。

首先，添加以下扩展：

extension MutableCollection where Self: BidirectionalCollection,
                                  Element: Comparable {
  mutating func quicksort() {
    quicksortLumuto(low: startIndex, high: index(before: endIndex))
  }

  private mutating func quicksortLumuto(low: Index, high: Index) {

  }
}

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

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

private mutating func quicksortLumuto(low: Index, high: Index) {
  if low <= high { // 1
    let pivotValue = self[high] // 2
    var p = self.partition { $0 > pivotValue } // 3

    if p == endIndex { // 4
      p = index(before: p)
    }
    // 5
    self[..<p].quicksortLumuto(low: low, high: index(before: p))
    // 6
    self[p...].quicksortLumuto(low: index(after: p), high: high)
  }
}

继续在集合上执行快速排序，直到开始和结束索引相互重叠。
Lumuto的分区总是取集合中的最后一个元素来执行分区。
对集合中的元素进行分割，并返回满足条件的第一个索引p，其中元素大于pivotValue。索引p之前的元素代表不满足谓词的元素，而p之后的元素代表满足条件的元素。
处理基本情况。如果p是最后一个索引，则移动到之前的索引。考虑下面的情况：

[8 3 2 8]
       p

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

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

在第一个分区上执行快速排序，该分区由不大于pivotValue的元素组成。
在第二个分区上进行快速排序，该分区由大于的元素组成。

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

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

Fun

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