萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 合併排序(歸並排序)演算法完整解析與兩種實作範例

什麼是合併排序?

合併排序是一種基於分治法的高效排序演算法。其核心思想是將陣列遞迴拆分為單一元素的子陣列,再將有序的子陣列兩兩合併,最終得到完整有序序列。時間複雜度穩定為 O(n log n),且屬於穩定排序。

合併操作步驟

  1. 申請空間,大小為兩個已排序序列長度之和。
  2. 設定兩個指標,分別指向兩序列起始位置。
  3. 比較指標所指元素,將較小者放入合併空間,並移動指標。
  4. 重複步驟 3 直到某一序列到達尾端。
  5. 將另一序列剩餘元素直接複製至合併序列尾部。

範例一:遞迴實作(現代 ES5+ 風格)

此版本使用 slice 與 concat 簡化陣列操作,程式碼精簡易讀:

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));
  }
}

// 測試
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
mergeSort(arr);
console.log(arr); // [1, 2, 3, 5, 12, 15, 23, 32, 66, 87]

範例二:傳統索引式實作(適合教學觀察過程)

此版本模擬底層陣列操作,並記錄每一趟排序結果,方便觀察合併過程:

var count = 0;

function mSort(source, dest, s, t) {
  var result = "";
  var m;
  var dest2 = [];

  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 += dest[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++];
    }
  }
  // 複製剩餘元素
  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];
  }
}

// 使用範例
var array = [12, 25, 32, 16, 18, 27, 59, 69, 36];
var dest = [];
mSort(array, dest, 0, array.length - 1);
console.log("最終結果:", dest);

效能比較與選擇建議

特性範例一範例二
程式碼簡潔度高中
記憶體額外開銷較大(頻繁建立新陣列)較小(原地操作)
適合場景一般應用、快速開發教學演示、記憶體受限環境

總結

合併排序以穩定的 O(n log n) 表現,是處理大量資料排序的首選演算法之一。理解其分治與合併機制,有助於掌握更多進階演算法的設計思想。

copyright © 萬盛學電腦網 all rights reserved