快速排序算法详解：从天真到优化

快速排序（Quicksort）是一种高效的排序算法，它采用分治法（Divide and Conquer）策略，将一个数组分为小于、等于和大于基准值的三部分，然后递归地排序这些部分。

本文将介绍三种快速排序的实现方式：天真快速排序、Lomuto 分区方案和三点取中法。

我们将通过具体的代码示例和适用场景来帮助理解这些算法。

天真快速排序

天真快速排序（Naive Quicksort）是快速排序的最简单实现。它通过选择一个基准值，将数组分为小于、等于和大于基准值的三部分，然后递归地排序这些部分。

实现代码

import Foundation

public func quicksortNaive<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else {
    return a
  }
  let pivot = a[a.count / 2]
  let less = a.filter { $0 < pivot }
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }
  return quicksortNaive(less) + equal + quicksortNaive(greater)
}

适用场景

天真快速排序适用于小型数组或对性能要求不高的场景。由于它多次遍历数组并创建中间数组，性能相对较差，不适合处理大型数组。

示例

let arr = [4, 5, 3, 7, 2, 8, 1, 6]
let sortedArr = quicksortNaive(arr)
print(sortedArr) // 输出: [1, 2, 3, 4, 5, 6, 7, 8]

Lomuto 分区方案

Lomuto 分区方案是一种更高效的快速排序实现。它通过选择数组的最后一个元素作为基准值，并在原地进行分区操作，从而减少了内存开销。

实现代码

import Foundation

public func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let pivot = a[high]
  var i = low
  for j in low..<high {
    if a[j] <= pivot {
      a.swapAt(i, j)
      i += 1
    }
  }
  a.swapAt(i, high)
  return i
}

public func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

适用场景

Lomuto 分区方案适用于中型数组和对性能有一定要求的场景。它通过原地分区减少了内存开销，但在某些情况下（如数组已部分排序）性能可能不太稳定。

示例

var arr = [4, 5, 3, 7, 2, 8, 1, 6]
quicksortLomuto(&arr, low: 0, high: arr.count - 1)
print(arr) // 输出: [1, 2, 3, 4, 5, 6, 7, 8]

三点取中法

三点取中法（Median of Three）是一种优化的快速排序实现。它通过选择数组的第一个元素、中间元素和最后一个元素中的中位数作为基准值，可以更好地应对某些特殊情况，从而提高排序效率。

实现代码

import Foundation

public func medianOfThree<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let center = (low + high) / 2
  if a[low] > a[center] {
    a.swapAt(low, center)
  }
  if a[low] > a[high] {
    a.swapAt(low, high)
  }
  if a[center] > a[high] {
    a.swapAt(center, high)
  }
  return center
}

public func quickSortMedian<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let pivotIndex = medianOfThree(&a, low: low, high: high)
    a.swapAt(pivotIndex, high)
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

适用场景

三点取中法适用于大型数组和对性能要求较高的场景。通过选择更合理的基准值，它可以减少最坏情况下的时间复杂度，通常能使快速排序算法表现更稳定。

示例

var arr = [4, 5, 3, 7, 2, 8, 1, 6]
quickSortMedian(&arr, low: 0, high: arr.count - 1)
print(arr) // 输出: [1, 2, 3, 4, 5, 6, 7, 8]

总结

通过以上三种快速排序算法的介绍，我们可以看到它们各自的优缺点和适用场景：

1. 天真快速排序：简单直观，适合小型数组，但性能较差。
2. Lomuto 分区方案：原地分区，减少内存开销，适合中型数组。
3. 三点取中法：选择更合理的基准值，提高性能，适合大型数组。

希望这篇文章能帮助你更好地理解快速排序算法，并在实际应用中选择合适的实现方式。

Happy Coding!

参考源码：https://github.com/MFiOS/quicksortDemo