Fork me on GitHub

排序算法-归并算法

归并排序(MERGE-SORT)基础

定义:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
实现过程:比较a[i]和b[j]的大小,若a[i]≤b[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素b[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

归并操作

归并排序:其基本思想是分治策略,先进行划分,然后再进行合并。

算法思路

假设要对数组C进行归并排序,步骤是:
let C = [10, 4, 6, 3, 8, 2, 5, 7];
1.先将C划分为两个数组A和B(即把数组C从中间分开 n = Math.floor(C.length/2))
2.再分别对数组A、B重复步骤1的操作,逐步划分,直到不能再划分为止(每个子数组只剩下一个元素),这样,划分的过程就结束了。
3.然后从下层往上层不断合并数组,每一层合并相邻的两个子数组,合并的过程是每次从待合并的两个子数组中选取一个最小的元素,然后把这个元素放到合并后的数组中,不断重复直到把两个子数组的元素都放到合并后的数组为止。
4.依次类推,直到合并到最上层结束,这时数据的排序已经完成了。

算法划分和合并过程


先划分: [10, 4, 6, 3, 8, 2, 5, 7]
第一次划分:[10, 4, 6, 3] [8, 2, 5, 7]
第二次划分:[10, 4] [6, 3] [8, 2] [5, 7]
第三次划分:[10] [4] [6] [3] [8] [2] [5] [7]
再合并:
第一次合并:[4, 10] [3, 6] [2, 8] [5, 7]
第二次合并:[3, 4, 6, 10] [2, 5, 7, 8]
第三次合并:[2, 3, 4, 5, 6, 7, 8, 10]

图解

代码实现

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
function merge(left, right){
var result=[];
while(left.length && right.length){
if(left[0] < right[0]){
/*shift()方法用于把数组的第一个元素从其中删除,并返回第一个元素的值。*/
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}

function mergeSort(items){
if(items.length === 1){
return items;
}
let middle = Math.floor(items.length/2),
left = items.slice(0, middle), //得到下标从0~index-1的数组
right = items.slice(middle); //得到下标从index开始到末尾的数组
return merge(mergeSort(left), mergeSort(right));
}

let arr = [10, 4, 6, 3, 8, 2, 5, 7];
let demo = mergeSort(arr)
console.log(arr); // [10, 4, 6, 3, 8, 2, 5, 7]
console.log(demo); // [2, 3, 4, 5, 6, 7, 8, 10]

ps:使用递归的代码如下。优点是描述算法过程思路清晰,缺点是使用递归,mergeSort()函数频繁地自我调用。长度为n的数组最终会调用mergeSort()函数 2n-1次,这意味着一个长度超过1500的数组会在Firefox上发生栈溢出错误。可以考虑使用迭代来实现同样的功能。
时间复杂度:O(n log n)
空间复炸都:O(n)
稳定性:稳定
排序方式:外排序

动图展示

动态图
图片来源,在此表示感谢

参考文档:
JS实现归并排序
js归并排序法
归并排序
十大经典排序算法

-------------本文结束感谢您的阅读,如果本文对你有帮助就记得给个star-------------
Donate comment here