Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


排序演算法筆記 4 - Merge Sort (合併排序法)

By Jimmy 2022-04-18
發表於 演算法 資工
排序演算法筆記 4 - Merge Sort (合併排序法)

Merge Sort (合併排序法) 是第一個要介紹的 efficient sort,和前面幾個排序演算法相比雖然會複雜一些,但時間複雜度相較之下也會比較好。

1. Merge Sort 方法一

1.1 JavaScript 實作

function mergeSort1(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    // 將陣列切半
    const middle = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, middle);
    const rightArr = arr.slice(middle, arr.length);
    // 合併排序好的兩半陣列
    return merge1(mergeSort1(leftArr), mergeSort1(rightArr));
  }
}

function merge1(leftArr, rightArr) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] > rightArr[rightIndex]) {
      result.push(rightArr[rightIndex]);
      rightIndex++;
    } else {
      result.push(leftArr[leftIndex]);
      leftIndex++;
    }
  }

  while (leftIndex < leftArr.length) {
    result.push(leftArr[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < rightArr.length) {
    result.push(rightArr[rightIndex]);
    rightIndex++;
  }

  return result;
}

2. Merge Sort 方法二

2.1 JavaScript 實作

function mergeSort2(arr, start = 0, end = arr.length - 1) {
  if (start === end) {
    return arr;
  } else {
    const middle = Math.floor((start + end) / 2);
    // 排序左半部
    mergeSort2(arr, start, middle);
    // 排序右半部
    mergeSort2(arr, middle + 1, end);
    // 將兩半部排序完的陣列合併
    merge2(arr, start, middle, end);
    return arr;
  }
}

function merge2(arr, start, middle, end) {
  const result = [];
  let leftIndex = start;
  let rightIndex = middle + 1;

  while (leftIndex <= middle && rightIndex <= end) {
    if (arr[leftIndex] < arr[rightIndex]) {
      result.push(arr[leftIndex]);
      leftIndex++;
    } else {
      result.push(arr[rightIndex]);
      rightIndex++;
    }
  }

  while (leftIndex <= middle) {
    result.push(arr[leftIndex]);
    leftIndex++;
  }

  while (rightIndex <= end) {
    result.push(arr[rightIndex]);
    rightIndex++;
  }

  for (let i = start; i <= end; i++) {
    arr[i] = result[i - start];
  }
}

3. Merge Sort 方法三

3.1 JavaScript 實作

function mergeSort3(arr) {
  const n = arr.length;
  for (let i = 1; i <= n; i *= 2) {
    for (let j = 0; j + i < n; j += 2 * i) {
      const start = j;
      const end = Math.min(j + i * 2 - 1, n - 1);
      const mid = j + i - 1;
      merge3(arr, start, mid, end);
    }
  }
  return arr;
}

function merge3(arr, start, middle, end) {
  const result = [];
  let leftIndex = start;
  let rightIndex = middle + 1;

  while (leftIndex <= middle && rightIndex <= end) {
    if (arr[leftIndex] < arr[rightIndex]) {
      result.push(arr[leftIndex]);
      leftIndex++;
    } else {
      result.push(arr[rightIndex]);
      rightIndex++;
    }
  }

  while (leftIndex <= middle) {
    result.push(arr[leftIndex]);
    leftIndex++;
  }

  while (rightIndex <= end) {
    result.push(arr[rightIndex]);
    rightIndex++;
  }

  for (let i = start; i <= end; i++) {
    arr[i] = result[i - start];
  }
}

4. Time Complexity

最佳:O(n log n)
最差:O(n log n)
平均:O(n log n)

4. 參考資料

大話資料結構(全新彩色版)
資料結構與演算法 (JavaScript)
JavaScript 學演算法(九)- 合併排序
一起用 JavaScript 來複習經典排序法吧!


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More