js 归并算法

发布时间:2019-08-10 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了js 归并算法脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

1.自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第2种方法)
2.自下而上的迭代

这里使用尾递归调用
ES6的尾递归优化只在严格模式下才会开启。
正常模式下,函数内部有两个变量,可以跟踪函数的调用栈。
func.arguments:返回调用时函数的参数。
func.caller:返回调用当前函数的那个函数。
尾调用优化发生时,函数的调用栈会改写,因此上面两个变量就会失真。严格模式禁用这两个变量,所以尾调用模式仅在严格模式下生效
始终都是O(n LOG n)的@R_227_1304@。代价是需要额外的内存空间

function mergeSort(arr) {

let len = arr.length;
if (len < 2) {
    return arr;
}

let middle = Math.floor(len/2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));

}

function merge(left, right) {

let result = [];

while (left.length &amp;& 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

}

const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(mergeSort(arr));

脚本宝典总结

以上是脚本宝典为你收集整理的js 归并算法全部内容,希望文章能够帮你解决js 归并算法所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。