DIV CSS 佈局教程網

JavaScript 排序算法實作:氣泡、快速與桶排序
編輯:關於JavaScript     

排序的基本概念

作為排序依據的資料項稱為「排序碼」,也就是資料元素的關鍵碼。為了便於查找,我們通常希望資料表按關鍵碼有序——有序表的折半查找效率遠高於線性掃描,而二叉排序樹、B-樹、B+ 樹的建構過程本身就是一個排序過程。

若關鍵碼是主關鍵碼,排序結果唯一;若是次關鍵碼,具有相同關鍵碼的元素之間,前後關係在排序後可能改變。若相同關鍵碼元素的相對位置在排序前後保持一致,稱此排序方法為穩定,否則為不穩定。

排序另可分為兩類:內排序指待排序列完全存放在記憶體中進行,適合規模不大的資料;外排序則在過程中需要存取外部儲存媒體,適用於大到無法全部放入記憶體的序列。

一、氣泡排序

/** @name 氣泡排序
 *  @desc 比較排序,複雜度 O(n*n)
 */
function BubbleSort(list) {
    var len = list.length;
    var cl, temp;
    while (len--) {
        cl = list.length;
        while (cl--) {
            if (list[cl] > list[len] && cl < len) {
                temp = list[len];
                list[len] = list[cl];
                list[cl] = temp;
            }
        }
    }
    return list;
}

二、快速排序

/** @name 快速排序
 *  @desc 比較排序,最差 O(n*n),最佳 O(nlogn)
 */
function QuickSort(list) {
    var i = 0;
    var j = list.length;
    var len = j;
    var left, right;
    var k = findK(i, j);
    if (k != 0) {
        var leftArr = [];
        var rightArr = [];
        var midArr = [list[k]];
        while (len--) {
            if (len != k) {
                if (list[len] > list[k]) {
                    rightArr.push(list[len]);
                } else {
                    leftArr.push(list[len]);
                }
            }
        }
        left = QuickSort(leftArr);
        right = QuickSort(rightArr);
        list = left.concat(midArr).concat(right);
    }
    return list;
}

function findK(i, j) {
    // 預設取中間位置作為基準
    return Math.floor((i + j) / 2);
}

快速排序的核心思想是分治:把待排序序列切成兩塊,从而降低整體複雜度;遞迴的巧用則是它的精妙之處。流程是先用 findK 找出一個基準元素,其餘元素與之比較,較大的收進一個集合、較小的收進另一個,再分別對兩集合排序。

它的效率主要取決於 findK 的實作與待排序資料的有序程度——基準選得越均勻,分割越平衡。也因為相同元素的相對位置會被打散,快速排序是不穩定的排序法。

三、桶排序:跳脫比較的框架

所有基於比較的排序法都有一個共同天花板:無論怎麼優化,平均排序時間必然隨元素數量增加而上升。非比較排序試圖繞過這個限制,讓時間複雜度趨向一個與資料量無關的穩定值,桶排序就是代表。

/** @name 桶排序
 *  @desc 非比較排序
 */
function BucketSort(list) {
    var len = list.length;
    var range = findMax(list);
    var result = [],
        count = [];
    var i, j;
    for (i = 0; i < range; i++) {
        count.push(0);
    }

    for (j = 0; j < len; j++) {
        count[list[j]]++;
        result.push(0);
    }
    for (i = 1; i < range; i++) {
        count[i] = count[i - 1] + count[i];
    }
    for (j = len - 1; j >= 0; j--) {
        result[count[list[j]]] = list[j];
        count[list[j]]--;
    }
    return result;
}

function findMax(list) {
    return MAX;
}

運作方式:先初始化一個長度為 MAX 的 count 陣列,把每個元素依其值放進對應位置並計數;接著累加 count,使第 n 個元素的值等於「值為 n 的元素在排序後的落點」;最後反向把元素映射進結果陣列。

桶排序的巧思在於:若一個元素在集合中是第 n 大,它就該排在第 n 位,完全不必關心前一位或後一位比它大還是小,也就是完全不必比較。

代價也很明顯:實務上資料值的範圍往往遠大於元素數量,因此必須配置一個巨大的 count 陣列。這也是為什麼桶排序的常見場景是外排序,而非記憶體內的一般排序。

有興趣的話,可以自己動手量測這三種排序在不同資料規模下的耗時曲線,會對「複雜度」這個概念有更直觀的體會。

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