js 归并算法

jimhs 发布于2019-08-23 14:55 / 786人阅读

摘要：正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。尾调用优化发生时，函数的调用栈会改写，因此上面两个变量就会失真。

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

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

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

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 && 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));

云服务器 GPU云服务器归并算法归并排序算法 python归并算法用c语言写归并算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101341.html

js归并排序算法的原理及简单demo

摘要：最近看了一道如何给阿里两万多名员工按照年龄排序的面试题后，很想记录下来自己的解题思路，下面综合考虑到基数较大和稳定性，我们采取归并排序的算法归并算法分为两个两个灵魂步骤，即拆分归并我们先把两万多名员工的基数缩小至六名员工的基数，他们的年龄数最近看了一道如何给阿里两万多名员工按照年龄排序的面试题后，很想记录下来自己的解题思路，下面：综合考虑到基数较大和稳定性，我们采取归并排序的算法；归...

TigerChain 2019-08-23 17:16 评论0 收藏0
js算法-归并排序（merge_sort）

摘要：归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。若将两个有序表合并成一个有序表，称为二路归并。归并排序归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是。归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并...

stormjun 2019-08-23 14:37 评论0 收藏0
JS数据结构与算法_排序和搜索算法

摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。上一篇：JS数据结构与算法_树写在前面这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...

姘搁『 2019-08-23 16:26 评论0 收藏0
JS排序算法

摘要：冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。插入排序最好情况下时间复杂度是，其他情况下也都是。代码演示插入排序归并排序原生里面的方法，在里面是用归并排序实现的，而在里面是用快速排序的变体来实现的。 1、冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。假设一共有n项，那么一共需要n-1趟，第一趟需要交换n-1次，但是第一趟结束后，最后一项基本确定就...

notebin 2019-08-01 15:39 评论0 收藏0