DIV CSS 佈局教程網

JavaScript 合併排序(Merge Sort)原理與兩種實作
編輯:JavaScript綜合知識     

合併排序是建立在「合併」操作上的排序法,也是分治法最典型的應用:先把序列切成子序列讓各自有序,再把有序的子序列逐層合併成完整的有序序列。若只合併兩個有序表,稱為二路合併。

合併操作的五個步驟

  1. 配置一塊大小等於兩個已排序序列總和的空间,用來存放結果
  2. 設定兩個指標,分別指向兩段序列的起點
  3. 比較兩個指標所指元素,把較小者放進結果並前進該指標
  4. 重複步驟三,直到其中一個指標抵達尾端
  5. 把另一段序列剩餘的元素直接接在結果後面

寫法一:遞迴加陣列操作

取中點切成左右兩半,各自遞迴排序後合併,再用 splice 把結果寫回原陣列,因此函式會回傳同一個陣列參考:

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

mergeSort([2, 1, 3, 12, 5, 66, 23, 87, 15, 32]);

寫法二:搭配來源與目標陣列

另一種常見寫法是把 source 與 dest 拆開,先遞迴排到暫存陣列,再由 merge 把兩段有序區間併回目標陣列,並在過程中輸出每一輪的排序結果,方便觀察合併的進行方式:

function mSort(source, dest, s, t) {
  var m, 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);
  }
  return dest;
}

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

特性小結

合併排序的時間複雜度穩定為 O(n log n),且是常見排序法中少數具穩定性的;代價是需要 O(n) 的額外空間。若資料量不大,實務上常會在子陣列小到一定程度時改用插入排序,以减少遞迴與配置成本。

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