DIV CSS 佈局教程網

JavaScript 排序演算法:合併排序(歸並排序)實戰兩例
編輯:JavaScript基礎知識     

合併排序(Merge sort)是建立在合併操作之上的一種高效排序演算法,也是分治法(Divide and Conquer)最典型的應用之一。

它的核心思路是把待排序序列拆成若干子序列,讓每個子序列各自有序,再將這些有序子序列合併成整體有序的序列。將兩個有序表合併成一個有序表,稱為 2-路歸並。

合併操作的步驟:

  1. 配置一個大小等於兩個已排序序列之和的空間,用來存放合併結果
  2. 設定兩個指標,分別指向兩個序列的起始位置
  3. 比較兩個指標所指元素,取較小者放入合併空間,並移動該指標
  4. 重複步驟 3,直到某一指標抵達序列尾端
  5. 把另一序列剩餘的元素直接複製到合併序列尾端

示例一:

function mergeSort(items) {
    if (items.length < 2) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));

    params.unshift(0, items.length);
    items.splice.apply(items, params);

    return items;

    function merge(left, right) {
        var result = [],
            il = 0,
            ir = 0;

        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        return result.concat(left.slice(il)).concat(right.slice(ir));
    }
}

// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
mergeSort(arr);

示例二:

<script type="text/javascript">
var count = 0;
// source 為來源陣列,dest 為目標陣列,s 為起始下標,t 為結束下標
function mSort(source, dest, s, t) {
    var result = "";
    var m;

    var dest2 = new Array();
    if (s == t) {
        dest[s] = source[s];
    } else {
        m = Math.floor((s + t) / 2);
        mSort(source, dest2, s, m);
        mSort(source, dest2, m + 1, t);
        merge(dest2, dest, s, m, t);
        result += "<br />第" + ++count + "遍排序的結果是:";
        for (var n = 0; n < dest.length; n++) {
            result += array[n] + ",";
        }
    }
    return result;
}

// 將兩個陣列依從小到大合併
function merge(source, dest, s, m, n) {
    for (var j = m + 1, k = s; j <= n && s <= m; k++) {
        if (source[s] < source[j]) {
            dest[k] = source[s++];
        } else {
            dest[k] = source[j++];
        }
    }
    // 將剩餘的有序元素補到 dest 末端
    if (s <= m) {
        for (var l = 0; l <= m - s; l++) {
            dest[k + l] = source[s + l];
        }
    }
    if (j <= n) {
        for (var l = 0; l <= n - j; l++) {
            dest[k + l] = source[j + l];
        }
    }
}
</script>
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved