DIV CSS 佈局教程網

JavaScript 快速排序實作與遞迴思路拆解
編輯:關於JavaScript     

核心代碼

function quickSort(arr) {
    // 長度小於 1 直接返回,作為遞迴終止條件
    if (arr.length < 1) {
        return arr;
    }

    // 取中間那個數作為基準點,索引若非整數則向下取整
    var centerIndex = Math.floor(arr.length / 2);
    var centerNum = arr.splice(centerIndex, 1);

    var arrLeft = [];    // 存放比基準小的
    var arrRight = [];   // 存放比基準大的

    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < centerNum) {
            arrLeft.push(arr[i]);
        } else if (arr[i] > centerNum) {
            arrRight.push(arr[i]);
        }
    }

    return quickSort(arrLeft).concat(centerNum, quickSort(arrRight));
}

var arrSort = [33, 18, 2, 40, 16, 63, 27];
console.log(quickSort(arrSort));

原理拆解

快速排序的三個動作:

找基準點——取陣列中間的一個數。

分區——以基準點為界,把剩下的數分成兩個新陣列,小的放左邊,大的放右邊。

遞迴——在函數內部呼叫自身,對左右兩個子陣列重複上述過程。

逐步追蹤

第一次執行:中間數是 40。迴圈中比 40 小的進 arrLeft,比 40 大的進 arrRight。

第二次呼叫:執行到 return quickSort(arrLeft).concat(centerNum, quickSort(arrRight)) 時,quickSort(arrLeft) 傳入的參數是 [33,18,2,16,27]。中間數是 2,比 2 小的放左邊,比 2 大的放右邊。

後面一樣是循環呼叫自己,直到傳入的參數長度小於 1,就把該參數返回,遞迴開始回捲並逐層拼接。

使用遞迴的三條經驗

  1. 必須有終止條件並返回一個值,否則就是死循環(或棧溢出)。
  2. 內部呼叫自己時傳入的參數要與初始參數相關聯,且規模必須在縮小,否則無法收斂。
  3. 執行同樣性質的工作時,可以考慮用遞迴來表達,代碼通常比迴圈版本更貼近問題本身。

幾個值得注意的細節

等於基準點的元素被丟掉了。上面用 < 和 > 兩個判斷,值等於 centerNum 的元素既不進 arrLeft 也不進 arrRight。示例陣列沒有重複值所以看不出問題,但 [5, 5, 5] 這樣的輸入會直接丟失資料。修正方式是把 >= 歸到某一側,或者改用三路分割(小於/等於/大於)。

splice 會修改原陣列。示例裡 arr.splice(centerIndex, 1) 直接把基準點從原陣列移除了,如果不想動到傳入的陣列,應該改用切片:var mid = arr[centerIndex],然後在迴圈裡跳過該索引。

concat 需要注意型別。centerNum 是 splice 返回的陣列(如 [40]),所以 concat(centerNum, ...) 正好能正確展開。如果改成存 arr[centerIndex] 得到的是數字,就要寫成 concat([centerNum], ...),否則 concat 仍會把它當單個元素追加,結果倒是相同,但語義容易誤解。

效能。這個實現每次都建立新陣列,額外的記憶體配置與拷貝開銷不小,平均時間複雜度是 O(n log n),但空間複雜度退化為 O(n)。生產環境的首選是原地分割(in-place)版本,空間可降到 O(log n)。

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