DIV CSS 佈局教程網

用 JavaScript 實作快速排序:基準點、雙陣列與遞迴
編輯:關於JavaScript     

這段程式碼來自「妙味課堂」的一期教學影片,我自己重寫並補上註解後記錄下來。

程式碼

function quickSort(arr) {
    // 長度不足 1 就直接返回,這是遞迴的出口
    if (arr.length < 1) {
        return arr;
    }

    // 取中間索引,浮點數要向下取整
    var centerIndex = Math.floor(arr.length / 2);

    // 用 splice 把基準點取出來
    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]);
        }
    }

    // 左右各自再排一次,然後用 concat 拼回來
    return quickSort(arrLeft).concat(centerNum, quickSort(arrRight));
}

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

三個關鍵動作

基準點:取陣列中間位置的那個數。

雙陣列分裝:以基準點為界,小的丟進左陣列,大的丟進右陣列。

遞迴:函數內部呼叫自己,直到子陣列長度小於 1 才停止。

寫遞迴時的三個注意事項

1. 一定要有一個會 return 的中止條件,否則就是死迴圈。

2. 內部呼叫自己時傳入的參數,要與首次傳入的參數存在關聯(這裡是「比基準點小/大的子集合」)。

3. 需要重複執行同一套動作的問題,就可以考慮用遞迴。

執行過程拆解

第一次呼叫,中間數是 40。迴圈判斷後,小於 40 的進 arrLeft,大於 40 的進 arrRight:

接著執行到 return quickSort(arrLeft).concat(centerNum, quickSort(arrRight)),quickSort(arrLeft) 收到的參數是 [33, 18, 2, 16, 27],這次的中間數是 2,比 2 小的放左邊,比 2 大的放右邊:

之後再呼叫 quickSort(arrRight),一路遞迴下去,直到傳入的陣列長度小於 1,就把該陣列原樣返回,這一層的排序才算完成。

這裡有個實作細節值得留意:centerNum 是陣列,因此比較時會發生型別轉換,雖然在數字範例中結果正確,若要更嚴謹可改成先取出純值再比較。

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