归并排序JavaScript实现_关于归并排序思路和代码实现

时间: 2018-01-24阅读: 2019标签: js知识

归并排序:其基本思想是分治策略,先进行划分,然后再进行合并。那么步骤如下: 


1.我们以数组[1, 5, 6, 2, 4, 3]举例,归并排序的第一步,将数组一分为2:

[1, 5, 6] [2, 4, 3]


2.接着将分成的数组继续一分为2,直到长度为1,我们构成如下二叉树(成树 从上往下):

[1, 5, 6, 2, 4, 3]
       /                 \
[1, 5, 6]             [2, 4, 3]
/       \            /         \
[1]    [5, 6]      [2]       [4, 3]
       /    \                /    \
      [5]   [6]             [4]   [3]


3.当递归到了尽头,我们向上回溯,对于两个有序的数组,我们将它们合并成一个有序数组,从而完成整个归并排序(归并 从下往上):

[1, 2, 3, 4, 5, 6]
       /                 \
[1, 5, 6]             [2, 3, 4]
/       \            /         \
[1]    [5, 6]      [2]       [3, 4]
       /    \                /    \
      [5]   [6]             [4]   [3]


直接上代码:  

function merge(left, right) {
  var tmp = [];

  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }

  return tmp.concat(left, right);
}

function mergeSort(a) {
  if (a.length === 1) 
    return a;

  var mid = ~~(a.length / 2)
    , left = a.slice(0, mid)
    , right = a.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}


这段合并排序的代码相当简单直观,但是mergeSort()函数会导致很频繁的自调用。一个长度为n的数组最终会调用mergeSort() 2*n-1次,这意味着如果需要排序的数组长度很大会在某些栈小的浏览器上发生栈溢出错误。

这里插个话题,关于递归调用时浏览器的栈大小限制,可以用代码去测试:

var cnt = 0;
try {
  (function() {
    cnt++;
    arguments.callee();
  })();
} catch(e) {
  console.log(e.message, cnt);
}


遇到栈溢出错误并不一定要修改整个算法,只是表明递归不是最好的实现方式。这个合并排序算法同样可以迭代实现,比如(摘抄自《高性能JavaScript》): 

function merge(left, right) {
  var result = [];

  while (left.length && right.length) {
    if (left[0] < right[0])
      result.push(left.shift());
    else
      result.push(right.shift());
  }

  return result.concat(left, right);
}

function mergeSort(a) {
  if (a.length === 1)
    return a;

  var work = [];
  for (var i = 0, len = a.length; i < len; i++)
    work.push([a[i]]);

  work.push([]); // 如果数组长度为奇数

  for (var lim = len; lim > 1; lim = ~~((lim + 1) / 2)) {
    for (var j = 0, k = 0; k < lim; j++, k += 2) 
      work[j] = merge(work[k], work[k + 1]);

    work[j] = []; // 如果数组长度为奇数
  }

  return work[0];
}

console.log(mergeSort([1, 3, 4, 2, 5, 0, 8, 10, 4]));

这个版本的mergeSort()函数功能与前例相同却没有使用递归。尽管迭代版本的合并排序算法比递归实现要慢一些,但它并不会像递归版本那样受调用栈限制的影响。把递归算法改用迭代实现是实现栈溢出错误的方法之一。  

 

站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/387

解密JavaScript执行上下文

首先我们先了解一下什么是执行上下文栈(Execution context stack)。分别展示了栈、堆和队列,其中栈就是我们所说的执行上下文栈;堆是用于存储对象这种复杂类型,我们复制对象的地址引用就是这个堆内存的地址

js基础_如何理解作用域和作用域链?

作用域外,无法引用作用域内的变量;离开作用域后,作用域的变量的内存空间会被清除,比如执行完函数或者关闭浏览器,作用域与执行上下文是完全不同的两个概念。我曾经也混淆过他们,但是一定要仔细区分。JavaScript代码的整个执行过程,分为两个阶段,代码编译阶段与代码执行阶段。

原生js判断当前页面是否为激活状态【判断用户是否在浏览当前页面】

但浏览器打开多个网页时候,如何判断我这个页面是否正在被用户浏览呢?我们可以通过document.hidden属性判断当前页面是否是激活状态。

js dom是什么?_JS中的DOM知识概览

JS中的DOM知识概览:文档对象模型,是针对 HTML 和 XML 文档的一个 API (应用程序编程接口), 描绘了一个层次化的节点树。 web 浏览器浏览一个页面的时候,DOM 就在幕后把你编辑的网页文档转换成一个文档对象。

原生js实现数组随机排列(数组乱序)的方法.【快速洗牌算法】

在开发中遇到这样的问题,需要将一组已知数组的顺序打乱,按照以前和现在的做法,总结了以下方法。

JavaScript 进阶问题列表

我在我的 Instagram 上每天都会发布 JavaScript 的选择题,并且同时也会在这个仓库中发布。从基础到进阶,测试你有多了解 JavaScript,刷新你的知识,或者帮助你的 coding 面试!

深入理解Javascript中apply、call、bind方法的总结。

apply 、 call 、bind 三者都是用来改变函数的this对象的指向的;第一个参数都是this要指向的对象,也就是想指定的上下文;都可以利用后续参数传参;bind 是返回对应函数,便于稍后调用;apply 、call 则是立即调用 。

JavaScript中公有、私有、静态、受保护的属性和方法

在开发中,我们需要限制某些属性和方法的暴露程度,使得它们不能通过对象实例本身被访问、修改或调用。要了解js面向对象,就必需先了解js中什么是公有、私有、静态、受保护。

js的微任务和宏任务

宏任务:当前调用栈中执行的代码成为宏任务。微任务: 当前(此次事件循环中)宏任务执行完,在下一个宏任务开始之前需要执行的任务,可以理解为回调事件。

js检测页面上一个元素是否已经滚动到了屏幕的可视区域内

只要页面加载了,其中在页面中出现的li就向控制台输出第几个发送请求;在本次加载的页面中,再将滚动条滚回前边的li,不再向控制台输出东西,也就是说已经显示过的li,不再向控制台输出东西。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!