共计 1516 个字符，预计需要花费 4 分钟才能阅读完成。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序
归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是 NlogN。
归并排序的 2 个步骤
先拆分，一直拆分到只有一个数
拆分完成后，开始递归合并
拆分过程
从上图可以看出，归并排序会将一个数组进行两两拆分，一直拆分到只有一个数的时候停止拆分。那么拆分的代码就很简单了，就是得到一个指向中间的指针 q，将数组拆分成 (start,p) 和（p，end）两个部分。
p 表示数组的开始下标
r 表示数组的结束下标
function divide(p, r){
return Math.floor((p + r) / 2 );
}
合并过程
合并的过程就如上图所示
遍历两组数据
进行对比大小
较小的那个值取出来放在第一个位置
举个例子：
假设现在数组 A 的数据是[2,5,1,3]
经过我们的拆分后会是(0,2),(2,4);
我们通过 A.slice(0,2)和 A.slice(2,4)=> 得到两个数组 A1[2,5]和 A2[1,3]
然后我们对数组 [2,5,1,3] 进行遍历，第一次会得到两边较小的数 1，第二次 2，第三次 3，第四次是 5
function merge(A, p, q, r){
const A1 = A.slice(p, q);
const A2 = A.slice(q, r);
// 哨兵，往 A1 和 A2 里 push 一个最大值，比如防止 A1 里的数都比较小，导致第三次遍历某个数组里没有值
A1.push(Number.MAX_SAFE_INTEGER);
A2.push(Number.MAX_SAFE_INTEGER);
// 循环做比较，每次取出较小的那个值
for (let i = p, j = 0, k = 0; i < r; i++) {
if (A1[j] < A2[k]) {
A[i] = A1[j];
j++;
} else {
A[i] = A2[k];
k++;
}
}
}
主程序
主程序就是做递归重复上面的操作了
function merge_sort(A, p = 0, r) {
r = r || A.length;
if (r – p === 1) {
return;
}
const q = divide(p, r);
merge_sort(A, p, q);
merge_sort(A, q, r);
merge(A, p, q, r);
return A;
}
完整代码
function divide(p, r) {
return Math.floor((p + r) / 2);
}
function merge(A, p, q, r) {
const A1 = A.slice(p, q);
const A2 = A.slice(q, r);
A1.push(Number.MAX_SAFE_INTEGER);
A2.push(Number.MAX_SAFE_INTEGER);
for (let i = p, j = 0, k = 0; i < r; i++) {
if (A1[j] < A2[k]) {
A[i] = A1[j];
j++;
} else {
A[i] = A2[k];
k++;
}
}
}
function merge_sort(A, p = 0, r) {
r = r || A.length;
if (r – p === 1) {
return;
}
const q = divide(p, r);
merge_sort(A, p, q);
merge_sort(A, q, r);
merge(A, p, q, r);
return A;
}
推荐阅读
数据结构系列：js 数据结构 - 栈 js 数据结构 - 链表 js 数据结构 - 队列 js 数据结构 - 二叉树（二叉堆）js 数据结构 - 二叉树（二叉搜索树）js 数据结构 - 散列表(哈希表)
