5、归并排序(Merge|5、归并排序(Merge Sort)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
5.1 算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列;
- 对这两个子序列分别采用归并排序;
- 将两个排序好的子序列合并成一个最终的排序序列。
![5、归并排序(Merge|5、归并排序(Merge Sort)](https://img.it610.com/image/info10/4406f9cc7296485999311b3b9c0e104a.gif)
文章图片
image 5.3 代码实现
function mergeSort(arr) {// 采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
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;
}
5.4 算法分析 【5、归并排序(Merge|5、归并排序(Merge Sort)】归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。
推荐阅读
- 一个人的碎碎念
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- Shell-Bash变量与运算符
- 清明,是追思、是传承、是感恩。
- 牛人进化+|牛人进化+ 按自己的意愿过一生
- 七老修复好敏感、角质层薄、红血丝
- 华为旁!大社区、地铁新盘,佳兆业城市广场五期!
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- 螃蟹和这些食物同吃,轻则腹泻、重则中毒!要小心哦~
- 八、「料理风云」