JavaScript 归并排序
🌙
手机阅读
本文目录结构
归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素，然后 将数组排序合并，最终合并为排序好的数组。
代码实现：
function mergeSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于0，直接返回，不需要排序
if (!Array.isArray(array) || length === 0) return;
if (length === 1) {
return array;
}
let mid = parseInt(length >> 1), // 找到中间索引值
left = array.slice(0, mid), // 截取左半部分
right = array.slice(mid, length); // 截取右半部分
return merge(mergeSort(left), mergeSort(right)); // 递归分解后，进行排序合并
}
function merge(leftArray, rightArray) {
let result = [],
leftLength = leftArray.length,
rightLength = rightArray.length,
il = 0,
ir = 0;
// 左右两个数组的元素依次比较，将较小的元素加入结果数组中，直到其中一个数组的元素全部加入完则停止
while (il < leftLength && ir < rightLength) {
if (leftArray[il] < rightArray[ir]) {
result.push(leftArray[il++]);
} else {
result.push(rightArray[ir++]);
}
}
// 如果是左边数组还有剩余，则把剩余的元素全部加入到结果数组中。
while (il < leftLength) {
result.push(leftArray[il++]);
}
// 如果是右边数组还有剩余，则把剩余的元素全部加入到结果数组中。
while (ir < rightLength) {
result.push(rightArray[ir++]);
}
return result;
}
归并排序将整个排序序列看成一个二叉树进行分解，首先将树分解到每一个子节点，树的每一层都是一个归并排序的过程，每 一层归并的时间复杂度为 O(n)，因为整个树的高度为 lgn，所以归并排序的时间复杂度不管在什么情况下都为O(nlogn)。
归并排序的空间复杂度取决于递归的深度和用于归并时的临时数组，所以递归的深度为 logn，临时数组的大小为 n，所以归 并排序的空间复杂度为 O(n)。
归并排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(n) ，是稳定排序。
详细资料可以参考： 《图解排序算法(四)之归并排序》 《归并排序的空间复杂度？》
更多面试题
如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。
| 面试题 | ||
|---|---|---|
| HTML | CSS | JavaScript |
| jQuery | Vue.js | React |
| 算法 | HTTP | Babel |
| BootStrap | Electron | Gulp |
| Node.js | 前端经验相关 | 前端综合 |
| Webpack | 微信小程序 | - |
这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！
