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

时间: 2018-01-24阅读: 1347标签: 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.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

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

关闭

js变量引用(指针)

基本类型:Number,Boolen,null,String,Underfined 存放在栈内存中,数据长度是固定的。引用类型:Object存在堆内存中,数据长度是变化的(同时有栈内存中有一个指针指向这个Object的)。

深入理解JS中引用类型和基本类型

javascript中基本类型指的是那些保存在栈内存中的简单数据段,即这种值完全保存在内存中的一个位置。 引用类型指那些保存在堆内存中的对象,意思是变量中保存的实际上只是一个指针,这个指针指向内存中的另一个位置,该位置保存对象。

js中bool值转换以及逻辑运算&&、||、 !!的使用

js作为一门弱类型语言,导致几乎所有数据都能转换为bool的类型,js转换 规则 。了解转换规则目的掌握逻辑运算符&&、||、 !!的使用

javascript怎么判断按钮被点击?

JavaScript可以通过Event对象的target事件或srcElement(IE浏览器支持)来判断按钮是否被点击。Event对象代表事件的状态,比如事件在其中发生的元素、键盘按键的状态、鼠标的位置、鼠标按钮的状态。

js的解析的两个阶段_预解析阶段、执行阶段

js不像C语言那样只要编译一次之后成.exe文件之后就不用在编译可以直接使用了,js是一种解释型语言,js同理是边解析边执行。js的解析分为两个阶段 1.预解析阶段 2.执行阶段。

js函数防抖与函数节流

直接绑定函数到scroll事件是非常错误的决定,当用户滚动页面时,页面可能会变得非常慢甚至未响应。而函数防抖和函数节流是解决这个问题的一种方式,通过限制需要经过的事件,直至再次调用函数,在处理一些高频率触发的 DOM 事件的时候,它们都能极大提高。

JavaScript中的特殊运算,一些有趣的js等式

JavaScript中的特殊运算,字符,true,false参与运算结果会怎么样?打开控制台。这会允许你再你的浏览器里输入下面所有的代码,所以你可以实时的看到发生什么了。

js中void 0 与 undefined

偶然看到一个问题:为什么有的编程规范要求用 void 0 代替 undefined?如果不知道这个答案的小伙伴,第一反应就要问void 0是什么鬼?

javascript怎么输出?

JavaScript怎么输出?输出方式有哪些?下面本篇文章就给大家介绍JavaScript的几种输出方式。window.alert()方法用于显示带有一条指定消息和一个【确认】 按钮的警告框。

10个JavaScript难点:能够读懂这篇博客的JavaScript开发者,运气不会太差…

10个JavaScript难点包括:立即执行函数,闭包,使用闭包定义私有变量,prototype,模块化,变量提升,柯里化,apply, call与bind方法,Memoization,函数重载

点击更多...

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