1.13 請?用Python?手寫實現(xiàn)快速排序 **步驟**: 1. 從數(shù)列中挑出?一個元素，稱為 “基準”（pivot）。 2. 重新排序數(shù)列，所有元素?比基準值?小的擺放在基準前?面，所有元素?比基準值?大的擺在基準的后?面（相同的數(shù)可以到任?一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。 3. 遞歸地（recursive）把?小于基準值元素的?子數(shù)列和?大于基準值元素的?子數(shù)列排序。 換?言之，**快速排序** 是基于分治模式處理的，對?一個典型?子數(shù)組 A[p...r] 排序的分治過程為三個步驟： 1. **分解**： ??A[p..r] 被劃分為倆個（可能空）的?子數(shù)組 A[p ..q-1] 和 A[q+1 ..r]，使得 A[p ..q-1] <= A[q] <= A[q+1 ..r]。 2. **解決**：通過遞歸調(diào)?用快速排序，對?子數(shù)組 A[p ..q-1] 和 A[q+1 ..r] 排序。 3. **合并**。 ```python QUICKSORT(A, p, r) 1 if p < r 2 then q ← PARTITION(A, p, r) #關鍵 3 QUICKSORT(A, p, q - 1) 4 QUICKSORT(A, q + 1, r) ``` **數(shù)組劃分**: 快速排序算法的關鍵是 PARTITION 過程，它對 A[p..r] 進?行行就地重排： ```python PARTITION(A, p, r) 1 x ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5 then i ← i + 1 6 exchange A[i] <-> A[j] 7 exchange A[i + 1] <-> A[r] 8 return i + 1 ``` 下圖是?一個例例?子： ?? 這是另外?一個可視化圖示：  **Python實現(xiàn)**： ```python def quick_sort(ary): ??return qsort(ary, 0, len(ary) - 1) def qsort(ary, left, right): ??# 快排函數(shù)，ary為待排序數(shù)組，left為待排序的左邊界，right為右邊界?? ??if left >= right: ????return ary ??key = ary[left]?# 取最左邊的為基準數(shù) ??lp = left?# 左指針 ??rp = right?# 右指針 ??while lp < rp: ????while ary[rp] >= key and lp < rp: ??????rp -= 1 ????while ary[lp] <= key and lp < rp: ??????lp += 1 ????ary[lp], ary[rp] = ary[rp], ary[lp] ??ary[left], ary[lp] = ary[lp], ary[left] ??qsort(ary, left, lp - 1) ??qsort(ary, rp + 1, right) ??return ary ``` 這段代碼是Python中快速排序的實現(xiàn)，它通過不斷地劃分子數(shù)組和遞歸地排序子數(shù)組來達到排序的目的。就像程序員中的快速思維一樣，讓數(shù)組在瞬間有序起來！?? 希望這個解答對你有所幫助！??