DIV CSS 佈局教程網

JavaScript 常見排序算法實測比較與源碼
編輯:關於JavaScript     

說明

寫這篇主要是為了自我練習,並無實用價值。每個瀏覽器測出來的數據都不一樣——以 Chrome 來說,快速排序通常最快;IE 則要依陣列長度而定,短陣列下希爾排序反而可能勝出。另外提醒一句:不要用太大的資料量去測氣泡排序(瀏覽器當掉我不負責)。

個人實測心得

  • 氣泡排序:最簡單也最慢,長度小於 7 時反而堪用。
  • 插入排序:比氣泡快,比快速與希爾慢,但在資料量小的情況下有其優勢。
  • 快速排序:非常快的一種排序法。V8 的 sort 實作就是快速排序與插入排序的結合。
  • 希爾排序:在非 Chrome 環境下,陣列長度小於 1000 時比快速排序更快。
  • 系統方法:Firefox 的原生 sort 實作非常快。

算法源碼

// ---------- 一些排序算法 ----------

// 利用原生 sort 排序
systemSort: function (array) {
    return array.sort(function (a, b) {
        return a - b;
    });
},

// 氣泡排序
bubbleSort: function (array) {
    var i = 0, len = array.length,
        j, d;
    for (; i < len; i++) {
        for (j = 0; j < len; j++) {
            if (array[i] < array[j]) {
                d = array[j];
                array[j] = array[i];
                array[i] = d;
            }
        }
    }
    return array;
},

// 快速排序
quickSort: function (array) {
    var i = 0;
    var j = array.length - 1;
    var Sort = function (i, j) {
        // 結束條件
        if (i == j) { return };
        var key = array[i];
        var stepi = i; // 記錄起始位置
        var stepj = j; // 記錄結束位置
        while (j > i) {
            // j 向前查找
            if (array[j] >= key) {
                j--;
            } else {
                array[i] = array[j]
                // i 向後查找
                while (j > ++i) {
                    if (array[i] > key) {
                        array[j] = array[i];
                        break;
                    }
                }
            }
        }
        // 若第一個取出的 key 就是最小值
        if (stepi == i) {
            Sort(++i, stepj);
            return;
        }
        // 最後一個空位留給 key
        array[i] = key;
        // 遞迴
        Sort(stepi, i);
        Sort(j, stepj);
    }
    Sort(i, j);
    return array;
},

// 插入排序
insertSort: function (array) {
    var i = 1, j, step, key,
        len = array.length;
    for (; i < len; i++) {
        step = j = i;
        key = array[j];
        while (--j > -1) {
            if (array[j] > key) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = key;
    }
    return array;
},

// 希爾排序
shellSort: function (array) {
    var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // 較小陣列的步長序列
    // var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035,
    //                428481, 90358, 19001, 4025, 836, 182, 34, 9, 1] // 大陣列用
    var i = 0;
    var stepArrLength = stepArr.length;
    var len = array.length;
    var len2 = parseInt(len / 2);
    for (; i < stepArrLength; i++) {
        if (stepArr[i] > len2) {
            continue;
        }
        stepSort(stepArr[i]);
    }

    // 對單一步長做插入排序
    function stepSort(step) {
        var i = 0, j = 0, f, tem, key;
        var stepLen = len % step > 0 ? parseInt(len / step) + 1 : len / step;

        for (; i < step; i++) {          // 依序遍歷每一列
            for (j = 1; step * j + i < len; j++) {  // 遍歷該列的每一行
                tem = f = step * j + i;
                key = array[f];
                while ((tem -= step) >= 0) {         // 向上查找插入點
                    if (array[tem] > key) {
                        array[tem + step] = array[tem];
                    } else {
                        break;
                    }
                }
                array[tem + step] = key;
            }
        }
    }
    return array;
}

幾點觀察

希爾排序之所以在中等規模陣列上表現亮眼,關鍵在步長序列的選擇。上面這組步長是依據維基百科上針對較小陣列的建議;大陣列則建議改用差距懸殊的序列(如註解中的那組),讓早期的分割更粗、後期收斂更細。

而快速排序那段實作刻意用「挖坑填數」的方式在原地搬移,避免了額外套用陣列,這也是它在實測中領先的原因之一。若要投入正式專案,直接用原生 sort 並提供比較函式,通常仍是最省事且足夠快的選擇。

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