DIV CSS 佈局教程網

JavaScript 與 Python 快速排序寫法對照
編輯:關於JavaScript     

快速排序是理解「分治」思維最經典的例子。有意思的是,在支援高階函式(把函式當作值傳遞)的語言裡,它的實作可以短到近乎 pseudocode。以下把 JavaScript 與 Python 兩個版本並排來看。

JavaScript 版本

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];
    })));
}

Python 版本

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) 先切掉頭再篩選,語意會更清楚。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved