归并排序（Merge Sort）
在计算机科学里，归并排序（Merge Sort）是一种通用有效的排序算法。通常情况下实现的是稳定的排序队列，这意味着相等元素排序后的顺序与排序前保持一致。归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用，由John von Neumann发明于1945年。
归并排序（Merge Sort）
例子
利用归并排序，对有7个整数值的数组进行排序。以下图示模拟归并排序（自上而下）的步骤。
归并排序步骤模拟图
复杂度
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
ES6实现
function MergeSort(array) {
let len = array.length;
if (len <= 1) {
return array;
}
let num = Math.floor(len / 2);
let left = MergeSort(array.slice(0, num));
let right = MergeSort(array.slice(num, array.length));
return merge(left, right);
function merge(left, right) {
let [l, r] = [0, 0];
let result = [];
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result.push(left[l]);
l++;
} else {
result.push(right[r]);
r++;
}
}
result = result.concat(left.slice(l, left.length));
result = result.concat(right.slice(r, right.length));
return result;
}
}
参考
相关阅读
JavaScript的排序算法——冒泡排序
JavaScript的排序算法——选择排序
JavaScript的排序算法——插入排序
JavaScript的排序算法——归并排序
JavaScript的排序算法——快速排序
