归并排序详解：原理、实现与应用场景

创作时间:

作者:

@小白创作中心

归并排序详解：原理、实现与应用场景

引用

来源

https://www.cnblogs.com/smileZAZ/p/18155964

一、是什么

归并排序（Merge Sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法的一个非常典型的应用。归并排序的基本思想是将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。

例如对于含有 (n) 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1）。然后进行两两合并，使 (n) 个有序表变为 (n/2) 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2 个大的有序表）。通过不断地进行两两合并，直到得到一个长度为 (n) 的有序表为止。

例如对无序表 ({49，38，65，97，76，13，27}) 进行归并排序，可以分为分、合两部分：

归并合过程中，每次得到的新的子表本身有序，所以最终得到有序表。上述分成两部分，则称为二路归并，如果分成三个部分则称为三路归并，以此类推。

二、如何实现

关于归并排序的算法思路如下：

分：把数组分成两半，再递归对子数组进行分操作，直至到一个个单独数字
合：把两个数合成有序数组，再对有序数组进行合并操作，直到全部子数组合成一个完整的数组
合并操作可以新建一个数组，用于存放排序后的数组
比较两个有序数组的头部，较小者出队并且推入到上述新建的数组中
如果两个数组还有值，则重复上述第二步
如果只有一个数组有值，则将该数组的值出队并推入到上述新建的数组中

用代码表示则如下：

function mergeSort(arr) { // 采用自上而下的递归方法
 const len = arr.length;
 if(len < 2) {
 return arr;
 }
 let middle = Math.floor(len / 2),
 left = arr.slice(0, middle),
 right = arr.slice(middle);
 return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
 const result = [];
 while (left.length && right.length) {
 if (left[0] <= right[0]) {
 result.push(left.shift());
 } else {
 result.push(right.shift());
 }
 }
 while (left.length)
 result.push(left.shift());
 while (right.length)
 result.push(right.shift());
 return result;
}

上述归并分成了分、合两部分，在处理分过程中递归调用两个分的操作，所花费的时间为2乘 (T(n/2))，合的操作时间复杂度则为 (O(n))，因此可以得到以下公式：

总的执行时间 = 2 × 输入长度为 (n/2) 的 sort 函数的执行时间 + merge 函数的执行时间 (O(n))

当只有一个元素时，(T(1) = O(1))

如果对 (T(n) = 2 * T(n/2) + O(n)) 进行左右 / n 的操作，得到 (T(n) / n = (n / 2) * T(n/2) + O(1))

现在令 (S(n) = T(n)/n)，则 (S(1) = O(1))，然后利用表达式带入得到 (S(n) = S(n/2) + O(1))

所以可以得到：

(S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S(1) + O(logn) = O(logn))

综上可得，(T(n) = n * log(n) = nlogn)

关于归并排序的稳定性，在进行合并过程，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也不会交换，由此可见归并排序是稳定的排序算法。