快速排序（Quicksort）是一種高效的排序算法杆融，它采用分治法（Divide and Conquer）策略楞卡，將一個(gè)數(shù)組分為小于、等于和大于基準(zhǔn)值的三部分，然后遞歸地排序這些部分蒋腮。
本文將介紹三種快速排序的實(shí)現(xiàn)方式：天真快速排序淘捡、Lomuto 分區(qū)方案和三點(diǎn)取中法。
我們將通過具體的代碼示例和適用場(chǎng)景來幫助理解這些算法池摧。
天真快速排序
天真快速排序（Naive Quicksort）是快速排序的最簡(jiǎn)單實(shí)現(xiàn)焦除。它通過選擇一個(gè)基準(zhǔn)值，將數(shù)組分為小于作彤、等于和大于基準(zhǔn)值的三部分膘魄，然后遞歸地排序這些部分。
實(shí)現(xiàn)代碼
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)
}
適用場(chǎng)景
天真快速排序適用于小型數(shù)組或?qū)π阅芤蟛桓叩膱?chǎng)景竭讳。由于它多次遍歷數(shù)組并創(chuàng)建中間數(shù)組创葡，性能相對(duì)較差，不適合處理大型數(shù)組绢慢。
示例
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 分區(qū)方案
Lomuto 分區(qū)方案是一種更高效的快速排序?qū)崿F(xiàn)灿渴。它通過選擇數(shù)組的最后一個(gè)元素作為基準(zhǔn)值，并在原地進(jìn)行分區(qū)操作呐芥，從而減少了內(nèi)存開銷。
實(shí)現(xiàn)代碼
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)
}
}
適用場(chǎng)景
Lomuto 分區(qū)方案適用于中型數(shù)組和對(duì)性能有一定要求的場(chǎng)景奋岁。它通過原地分區(qū)減少了內(nèi)存開銷思瘟，但在某些情況下（如數(shù)組已部分排序）性能可能不太穩(wěn)定。
示例
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]
三點(diǎn)取中法
三點(diǎn)取中法（Median of Three）是一種優(yōu)化的快速排序?qū)崿F(xiàn)闻伶。它通過選擇數(shù)組的第一個(gè)元素滨攻、中間元素和最后一個(gè)元素中的中位數(shù)作為基準(zhǔn)值，可以更好地應(yīng)對(duì)某些特殊情況蓝翰，從而提高排序效率光绕。
實(shí)現(xiàn)代碼
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)
}
}
適用場(chǎng)景
三點(diǎn)取中法適用于大型數(shù)組和對(duì)性能要求較高的場(chǎng)景。通過選擇更合理的基準(zhǔn)值畜份，它可以減少最壞情況下的時(shí)間復(fù)雜度诞帐，通常能使快速排序算法表現(xiàn)更穩(wěn)定。
示例
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]
總結(jié)
通過以上三種快速排序算法的介紹爆雹，我們可以看到它們各自的優(yōu)缺點(diǎn)和適用場(chǎng)景：
- 天真快速排序：簡(jiǎn)單直觀停蕉，適合小型數(shù)組，但性能較差钙态。
- Lomuto 分區(qū)方案：原地分區(qū)慧起，減少內(nèi)存開銷，適合中型數(shù)組册倒。
- 三點(diǎn)取中法：選擇更合理的基準(zhǔn)值蚓挤，提高性能，適合大型數(shù)組。
希望這篇文章能幫助你更好地理解快速排序算法灿意，并在實(shí)際應(yīng)用中選擇合適的實(shí)現(xiàn)方式估灿。
Happy Coding!
