x-note
Search…
归并排序
归并排序(Merge Sort)是一种基于归并操作的排序算法,核心思想是将两个已经排序的序列合并成一个序列。
  • 平均时间复杂度:
    O(nlog2n)O({n}\log_{2}{n})
  • 最好时间复杂度:
    O(n)O(n)
  • 最坏时间复杂度:
    O(nlog2n)O({n}\log_{2}{n})
  • 空间复杂度:
    O(n)O(n)
  • 稳定性:稳定
  • 排序方式:非原地(Not-in-place)
归并算法又分为自顶下下(Top-down)自底向上(Bottom-up)两种实现方式

自顶向下实现

  1. 1.
    申请一大小为俩个已排序序列之和的空间
  2. 2.
    始比较两个序列中的第一个元素,相对较小的元素放入之前申请的空间
  3. 3.
    取出较小元素所在队列的下一个元素,然后与另一队列之前取出的元素进行比较
  4. 4.
    重复步骤 2~3 直到某个队列提前遍历完成
  5. 5.
    将另一序列的所有元素直接放入申请的空间尾部
Could not load image
具体实现:
1
// 以下 JavaScript 版本的实现利用了基础库 Array 的特有 API
2
// 并未考虑达到到最优的空间和时间,仅为了体现核心思想
3
function mergeSortTopDown(arr) {
4
function core(arr1, arr2) {
5
const rest = [];
6
while (arr1.length && arr2.length) {
7
rest.push(arr1[0] <= arr2[0] ? arr1.shift() : arr2.shift());
8
}
9
return rest.concat(arr1.concat(arr2));
10
}
11
const len = arr.length;
12
if (len < 2) {
13
return arr;
14
}
15
let mid = parseInt(len / 2);
16
return core(mergeSortTopDown(arr.slice(0, mid)), mergeSortTopDown(arr.slice(mid)));
17
}
Copied!

自底向上实现

自底向上就是把序列当作是由 n 个长度为 1 的子序列组成的序列,然后以 2 个序列为单元循环来回地合并子序列
  1. 1.
    将长度为 n 的序列拆分成 n 个子序列
  2. 2.
    每两个相邻的子序列进行归并操作,n 个子序列变成了
    ceil(n2)ceil(\dfrac{n}{2})
    个新的子序列
  3. 3.
    对所有新的子序列,重复步骤 2,知道最终得到一个长度为 n 的子序列
Could not load image
具体实现:
1
function mergeSort(arr) {
2
const len = arr.length;
3
if(arr.length < 2){
4
return;
5
}
6
7
for (let step = 1; step < len; step *= 2) {
8
for (let i = 0; i < len; i = i + 2 * step) {
9
mergeArrays(
10
arr,
11
i,
12
Math.min(i + step, len),
13
Math.min(i + 2 * step, len)
14
);
15
};
16
}
17
18
//对左右序列进行排序
19
function mergeArrays(arr, left, right, end) {
20
let n = left,
21
m = right;
22
const currentSort = [];
23
24
for (let j = left; j < end; j++) {
25
if ( n < right && ( m >= end || arr[n] < arr[m] )) {
26
currentSort.push(arr[n]);
27
n++;
28
} else {
29
currentSort.push(arr[m]);
30
m++;
31
}
32
}
33
//
34
currentSort.forEach(function(item, index) {
35
arr[left + index] = item;
36
});
37
}
38
39
return arr;
40
}
Copied!