快速排序是理解「分治」思維最經典的例子。有意思的是,在支援高階函式(把函式當作值傳遞)的語言裡,它的實作可以短到近乎 pseudocode。以下把 JavaScript 與 Python 兩個版本並排來看。
function quicksort(arr) {
if (arr.length <= 1) return arr;
return quicksort(arr.filter(function (lt, i) {
return i > 0 && lt < arr[0];
}))
.concat([arr[0]])
.concat(quicksort(arr.filter(function (ge, i) {
return i > 0 && ge >= arr[0];
})));
}
def quicksort(arr):
if len(arr) <= 1:
return arr
return quicksort([lt for lt in arr[1:] if lt < arr[0]]) \
+ a[0:1] + \
quicksort([ge for ge in arr[1:] if ge >= arr[0]])
把語法差異剝掉之後,兩個版本走的是完全相同的三步驟:
1. 終止條件。長度 0 或 1 的陣列本身就是已排序的,直接回傳。這一步是所有遞迴的 safety net,少了它就會無限遞迴。
2. 選基準並分區。取第一個元素當基準(pivot),把其餘元素分成「比它小」和「不比它小」兩堆。JavaScript 用 filter,Python 用列表 comprehension,本質都是一次篩選。
3. 合併。左堆排序後、基準、右堆排序後依序串接起來。JavaScript 用 concat,Python 直接用 + 運算子。
Python 範例中 a[0:1] 是原作者的筆誤,應為 arr[0:1];寫成切片而非 [arr[0]] 的用意是保持回傳型別一致(切片永遠得到 list),這是 Python 中常見的防呆技巧。
另外,這兩個版本雖然簡潔,卻都不是實務上的好選擇:每次都建立新陣列,額外的記憶體配置與複製成本遠高於原地(in-place)版本。它的價值在於把演算法意圖表達得一清二楚——當你能用兩三行說明白快速排序,再去看 Hoare 或 Lomuto 的分區寫法,會更容易理解那些看似艱澀的索引操作在做什麼。
小提醒:JavaScript 的 filter 回呼中加上 i > 0 是為了排除基準本身,若改用 arr.slice(1) 先切掉頭再篩選,語意會更清楚。