关闭

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

时间: 2018-01-24阅读: 1578标签: 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

document.write和innerHTML的区别

document.write只能重绘整个页面,innerHTML可以重绘页面的一部分。 document.write是直接写入到页面的内容流,如果在写之前没有调用document.open, 浏览器会自动调用open。

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

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

你不知道的 js 保留字

先是笼统的说一下有什么保留字,保留字的话根据犀牛书的划分,可有分为以下几类:基础保留字、严格模式下的保留字、严格模式下的不完全保留字、ECMAScript3的保留字、ECMAScipt 5 的保留字、全局变量和函数

javascript怎么判断按钮被点击?

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

为什么javascript不起作用?

JavaScript是一种属于网络的脚本语言,已经被广泛用于Web应用开发,常用来为网页添加各式各样的动态功能,为用户提供更流畅美观的浏览效果。通常JavaScript脚本是通过嵌入在HTML中来实现自身的功能的。

Js常用基础算法

冒泡排序;插入排序 过程就像你拿到一副扑克牌然后对它排序一样;快速排序;回文字符串;翻转字符串;字符串中出现最多次数的字符;数组去重;二分查找

JavaScript 优雅的实现方式包含你可能不知道的知识点【转】

Js优雅的实现方式包含你可能不知道的知识点:简短优雅地实现 sleep 函数,js获取时间戳,js数组去重,js数字格式化,js交换两个整数,将 argruments 对象(类数组)转换成数组,数字取整等

适配器在JavaScript中的体现

适配器设计模式在JavaScript中非常有用,在处理跨浏览器兼容问题、整合多个第三方SDK的调用,都可以看到它的身影。适配器模式是一种软件设计模式,允许从另一个接口使用现有类的接口。它通常用于使现有的类与其他类一起工作,而无需修改其源代码。

js浮点数精度丢失问题_如何解决js中浮点数计算不精准?

理解javascript中浮点数计算不精准的原因,如何解决浮点数的四则运算(加减乘除)。js中除了toFixed方法以外的实现方法总汇

Javascript实现模仿接口的3种方式

Javascript模仿接口可以有三种方式:1.注释法,此方法属于程序文档范畴,对接口的继承实现完全依靠程序员自觉 2.检查属性法,把要实现的接口方法添加到类属性列表里,通过定义好的检测反复检查是否已经实现了那些方法 3.鸭式辨形法

点击更多...

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