x-note
Search…
归并排序
归并排序（Merge Sort）是一种基于归并操作的排序算法，核心思想是将两个已经排序的序列合并成一个序列。
- 平均时间复杂度：
- 最好时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：
- 稳定性：稳定
- 排序方式：非原地（Not-in-place）
归并算法又分为自顶下下（Top-down）和自底向上（Bottom-up）两种实现方式
自顶向下实现
- 1.申请一大小为俩个已排序序列之和的空间
- 2.始比较两个序列中的第一个元素，相对较小的元素放入之前申请的空间
- 3.取出较小元素所在队列的下一个元素，然后与另一队列之前取出的元素进行比较
- 4.重复步骤 2~3 直到某个队列提前遍历完成
- 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.将长度为 n 的序列拆分成 n 个子序列
- 2.每两个相邻的子序列进行归并操作，n 个子序列变成了个新的子序列
- 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!
Last modified 3yr ago