/

JavaScript 算法：合併排序

JavaScript 算法：合併排序

合併排序是一種使用「分治法」概念的排序算法。

給定一個數組，我們首先將其分為兩個數組。

然後我們遞歸執行此操作，直到獲得只有一個元素的數組。

然後，我們從頭開始構建有序數組，通過對獲得的個別元素進行排序。

假設我們的數組是：

1
[4, 3, 1, 2]

我們首先將數組分成兩個：

1
2
[4, 3]
[1, 2]

然後我們遞歸地分割這些數組：

1
2
[4]
[3]

和

1
2
[1]
[2]

然後，通過首先對這些元素對進行排序，我們開始構建結果：

1
2
[3, 4]
[1, 2]

然後我們將這兩個數組合併：

1
[1, 2, 3, 4]

讓我們再舉一個具有更多項的數組的例子，這次使用字母：

1
['e', 'g', 'a', 'd', 'f', 'c', 'b']

我們將數組分成兩部分：

1
2
['e', 'g', 'a']
['d', 'f', 'c', 'b']

然後我們將第一個數組再分成兩部分：

1
2
['e']
['g', 'a']

然後分割第二個結果：

1
2
['g']
['a']

我們現在取原始數組的第二部分，再分成兩個：

1
2
['d', 'f']
['c', 'b']

我們分割兩個項目：

1
2
['d']
['f']
1
2
['c']
['b']

現在，我們有一系列只有一個元素的數組：

1
2
3
4
5
6
7
['e']
['g']
['a']
['d']
['f']
['c']
['b']

現在，我們將它們按成對排序：

1
2
3
4
['e', 'g']
['a', 'd']
['d', 'f']
['c', 'b']

然後我們對前兩個數組和最後兩個數組進行排序：

1
2
['a', 'd', 'e', 'g']
['c', 'b', 'd', 'f']

最後，我們合併獲得的兩個數組：

1
['a', 'b', 'c', 'd', 'e', 'f', 'g']

我們可以使用兩個函數來實現此算法。第一個叫做 mergeSort，這是我們將要調用的函數，另一個叫做 _mergeArrays，它負責合併數組。我在它的名字前加了 _，表示它不應該直接調用。

以下是實現的代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const _mergeArrays = (a, b) => {
  const c = [];

  while (a.length && b.length) {
    c.push(a[0] > b[0] ? b.shift() : a.shift());
  }

  // 如果還有值，將其添加到 `c` 的末尾
  while (a.length) {
    c.push(a.shift());
  }
  while (b.length) {
    c.push(b.shift());
  }

  return c;
}

const mergeSort = (a) => {
  if (a.length < 2) return a;
  const middle = Math.floor(a.length / 2);
  const a_l = a.slice(0, middle);
  const a_r = a.slice(middle, a.length);
  const sorted_l = mergeSort(a_l);
  const sorted_r = mergeSort(a_r);
  return _mergeArrays(sorted_l, sorted_r);
}

請注意，在 _mergeArrays() 函數中，我們初始化一個結果數組 c，並通過將傳遞給函數的 a 和 b 數組的值按值排序來填充它。在數組上調用 shift() 會刪除數組的第一個項目並返回該項目，因此我們將其傳遞給 c.push() 來將其添加到 c 數組中。

該算法的時間複雜度是 O(n log(n))，因此它非常高效。

tags: [“JavaScript”, “Algorithms”, “Sorting”]