快速排序（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]
总结
通过以上三种快速排序算法的介绍，我们可以看到它们各自的优缺点和适用场景：
- 天真快速排序：简单直观，适合小型数组，但性能较差。
- Lomuto 分区方案：原地分区，减少内存开销，适合中型数组。
- 三点取中法：选择更合理的基准值，提高性能，适合大型数组。
希望这篇文章能帮助你更好地理解快速排序算法，并在实际应用中选择合适的实现方式。
Happy Coding!
