快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
本質(zhì)上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
基本思想是, 通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。
算法過程描述
- 從數(shù)列中挑出一個元素，稱為 “基準”（pivot）；
- 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
- 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
如果要排序數(shù)組中下標從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到 r 之間的任意一個數(shù)據(jù)作為 pivot (分區(qū)點), 我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的。
邏輯演示
剩下, 可以用遞歸排序下標從 p 到 q-1 之間的數(shù)據(jù)和下標從 q+1 到 r 之間的數(shù)據(jù)，直到區(qū)間縮小為 1，就說明所有的數(shù)據(jù)都有序了。
動圖演示
quickSort.gif
復雜度
用大O表示法，忽略常量、低階和常數(shù)系數(shù)。
時間復雜度為：最壞O(n2), 最好O(nlogn)
空間復雜度為：并未開辟額外空間, 所以為O(1)
穩(wěn)定性: 不穩(wěn)定
代碼實現(xiàn)(Swift)
var numbers = [6,8,7,6,3,5,9,4]
func quickSort(numbers: inout [Int], leftIndex: Int, rightIndex: Int) {
if leftIndex >= rightIndex {
return
}
var i = leftIndex;
var j = rightIndex;
// 記錄比較基準數(shù)
var pivot = numbers[i]
while i < j {
// 首先從右邊j開始查找比基準數(shù)小的值
while i < j && numbers[j] >= pivot {
// 如果比基準數(shù)大，不需要做什么操作, 接續(xù)往前查找
j -= 1
}
// 如果比基準數(shù)小，則將查找到的小值調(diào)換到i的位置
numbers[i] = numbers[j]
print("\n\(numbers) bigger change \(j)th to \(i)th")
// 當在右邊查找到一個比基準數(shù)小的值時，就從i開始往后找比基準數(shù)大的值
while i < j && numbers[i] <= pivot {
// 如果比基準數(shù)小，不需要做什么操作, 接續(xù)往后查找
i += 1
}
// 如果比基準數(shù)大，則將查找到的大值調(diào)換到j的位置
numbers[j] = numbers[i]
print("\n\(numbers) smaller change \(i)th to \(j)th")
}
// 比較一次之后, 將基準數(shù)放到正確位置
numbers[i] = pivot;
print("\n\(numbers)")
/**** 遞歸排序 ***/
// 排序基準數(shù)左邊的
quickSort(numbers: &numbers, leftIndex: leftIndex, rightIndex: i-1)
// 排序基準數(shù)右邊的
quickSort(numbers: &numbers, leftIndex: i+1, rightIndex: rightIndex)
}
quickSort(numbers: &numbers, leftIndex: 0, rightIndex: numbers.count-1)
print(numbers)
終端打印結(jié)果：
[4, 8, 7, 6, 3, 5, 9, 4] bigger change 7th to 0th
[4, 8, 7, 6, 3, 5, 9, 8] smaller change 1th to 7th
[4, 5, 7, 6, 3, 5, 9, 8] bigger change 5th to 1th
[4, 5, 7, 6, 3, 7, 9, 8] smaller change 2th to 5th
[4, 5, 3, 6, 3, 7, 9, 8] bigger change 4th to 2th
[4, 5, 3, 6, 3, 7, 9, 8] smaller change 4th to 4th
[4, 5, 3, 6, 6, 7, 9, 8]
[3, 5, 3, 6, 6, 7, 9, 8] bigger change 2th to 0th
[3, 5, 5, 6, 6, 7, 9, 8] smaller change 1th to 2th
[3, 5, 5, 6, 6, 7, 9, 8] bigger change 1th to 1th
[3, 5, 5, 6, 6, 7, 9, 8] smaller change 1th to 1th
[3, 4, 5, 6, 6, 7, 9, 8]
[3, 4, 5, 6, 6, 7, 9, 8] bigger change 2th to 2th
[3, 4, 5, 6, 6, 7, 9, 8] smaller change 2th to 2th
[3, 4, 5, 6, 6, 7, 9, 8]
[3, 4, 5, 6, 6, 7, 9, 8] bigger change 5th to 5th
[3, 4, 5, 6, 6, 7, 9, 8] smaller change 5th to 5th
[3, 4, 5, 6, 6, 7, 9, 8]
[3, 4, 5, 6, 6, 7, 8, 8] bigger change 7th to 6th
[3, 4, 5, 6, 6, 7, 8, 8] smaller change 7th to 7th
[3, 4, 5, 6, 6, 7, 8, 9]
[3, 4, 5, 6, 6, 7, 8, 9]
- 穩(wěn)定性
如果數(shù)組中有兩個相同的元素，比如測試的序列numbers: (6，8，7，6，3，5，9，4)，在經(jīng)過第一次分區(qū)操作之后，兩個 6 的相對先后順序就會改變。所以，
快速排序并不是一個穩(wěn)定的排序算法。
- 快速排序的性能分析
最好的情況下, 選擇的 pivot 都很合適，正好能將大區(qū)間對等地一分為二。這時快排的時間復雜度遞推求解公式跟歸并是相同的。即為O(nlogn)。
最壞的情況下, 有序數(shù)組中, 每次選擇最后一個元素作為 pivot，那每次分區(qū)得到的兩個區(qū)間都是不均等的。我們需要進行大約 n 次分區(qū)操作，才能完成快排的整個過程。每次分區(qū)我們平均要掃描大約 n/2 個元素，快排的時間復雜度就從 O(nlogn) 退化成了 O(n2).
T(n) 在大部分情況下的時間復雜度都可以做到 O(nlogn)，只有在極端情況下，才會退化到 O(n2)。
回目錄:常用的排序算法
結(jié)語
路漫漫其修遠兮，吾將上下而求索~
.End
