深入解析快速排序
一、分治策略分解
-
分解階段:
- 選擇基準元素 $pivot$
- 將數組劃分為三個子集: $$ left = {x | x < pivot} $$ $$ equal = {x | x = pivot} $$ $$ right = {x | x > pivot} $$
-
遞歸排序:
- 對 left 和 right 子集遞歸調用快速排序
- 遞歸終止條件:當子集長度 $\leq 1$ 時直接返回
-
合并結果: $$ sorted_arr = quick_sort(left) + equal + quick_sort(right) $$
二、時間復雜度分析
情況 | 時間復雜度 | 發生條件 |
---|---|---|
最優 | $O(n \log n)$ | 每次劃分完全平衡 |
最差 | $O(n^2)$ | 輸入已排序+固定基準選擇 |
平均 | $O(n \log n)$ | 隨機化基準選擇 |
數學推導(平均情況): $$ T(n) = 2T(\frac{n}{2}) + O(n) $$ 應用主定理可得 $T(n) = O(n \log n)$
三、基準選擇優化
-
隨機選擇法:
import random pivot_index = random.randint(0, len(arr)-1) arr[0], arr[pivot_index] = arr[pivot_index], arr[0] # 交換到首位
-
三數取中法:
- 取首、中、尾三個元素
- 選擇中間值作為基準
-
中位數法:
- 每9個元素為一組取中位數
- 遞歸求取近似中位數
四、分區算法對比
Lomuto分區法:
def partition(arr, low, high):pivot = arr[high]i = lowfor j in range(low, high):if arr[j] < pivot:arr[i], arr[j] = arr[j], arr[i]i += 1arr[i], arr[high] = arr[high], arr[i]return i
Hoare分區法(效率更高):
def partition(arr, low, high):pivot = arr[(low + high) // 2]i = low - 1j = high + 1while True:i += 1while arr[i] < pivot: i += 1j -= 1while arr[j] > pivot: j -= 1if i >= j: return jarr[i], arr[j] = arr[j], arr[i]
五、工程優化技巧
- 混合排序:當子數組長度 < 15 時切換為插入排序
- 尾遞歸優化:減少遞歸調用棧深度
- 重復元素處理:三向切分法(Dijkstra提出的荷蘭國旗問題解法)
def quick_sort_3way(arr, low, high):if low >= high: returnlt, i, gt = low, low, highpivot = arr[low]while i <= gt:if arr[i] < pivot:arr[lt], arr[i] = arr[i], arr[lt]lt += 1i += 1elif arr[i] > pivot:arr[i], arr[gt] = arr[gt], arr[i]gt -= 1else:i += 1quick_sort_3way(arr, low, lt-1)quick_sort_3way(arr, gt+1, high)
六、空間復雜度分析
- 最優情況:$O(\log n)$ (遞歸棧深度)
- 最差情況:$O(n)$
- 通過尾遞歸優化可將空間復雜度穩定在 $O(\log n)$
七、實際應用場景
- 內置排序算法實現(如Java的Arrays.sort())
- 大數據排序(結合外排序技術)
- 需要原地排序的場合(內存受限環境)
- 快速選擇算法(Top K問題)的基礎
八、穩定性分析
快速排序是不穩定的排序算法,改進方法:
def stable_quick_sort(arr):if len(arr) <= 1: return arrpivot = arr[0]return (stable_quick_sort([x for x in arr if x < pivot]) +[x for x in arr if x == pivot] +stable_quick_sort([x for x in arr if x > pivot]))
注:這種方法會破壞原地排序特性,但能保持穩定性