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

时间: 2018-01-24阅读: 345标签: 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()函数功能与前例相同却没有使用递归。尽管迭代版本的合并排序算法比递归实现要慢一些,但它并不会像递归版本那样受调用栈限制的影响。把递归算法改用迭代实现是实现栈溢出错误的方法之一。  

 

js中offset、scroll、event、client的区别和使用

用一句话概述:offset用于获取元素的实际显示尺寸 , scroll用于获取滚动后全部尺寸 , client用于获取不包括滚动条的实际显示尺寸,event用于获取鼠标的坐标位置。下面就详细介绍它们之间的使用和区别

js判断日期是否为今天

需求如下:后端返回字符串数据,需要前端判断该日期是否为今天。比如返回日期格式为:2018-08-14,那么需要如何来实现呢,这篇文章整理实现的几种方式供大家参考。

javascript中的伪线程,使用setTimeout模拟一个多线程

浏览器的内核是多线程的,一个浏览器一般至少实现三个常驻线程:javascript引擎线程,GUI渲染线程,浏览器事件触发线程。当我们要循环过百万级的数据甚至亿的时候怎么办?那就用setTimeout模拟一个多线程。

web worker是什么?理解并使用web worker

Web Worker 是为了解决 JavaScript 在浏览器环境中没有多线程的问题。正常形况下,浏览器执行某段程序的时候会阻塞直到运行结束后在恢复到正常状态,而HTML5的Web Worker就是为了解决这个问题,提升程序的执行效率。

JS方法整理_js常用函数大全

都是日常工作中使用的一些js方法,整理出来以便大家学习使用。主要包括:Js获取页面地址参数 、千分位 、判断是否数字 、图片按比例压缩、截取指定字节数的字符串、判断是否微信 、获取时间格式的几个举例 、获取字符串字节长度 、对象克隆、深拷贝 ...

Performance_js中计算网站性能监控利器

Performance提供的方法可以灵活使用,获取到页面加载等标记的耗时情况。Performance.timing属性对象提供了浏览器从打开网页到加载完成之间各个节点的耗时数据,包括重定向开始、DNS查询、浏览器响应数据、DOM解析等相关节点

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

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

浅谈js自记忆函数

最近阅读《JavaScript忍者秘籍》看到了一种有趣的函数:自记忆函数。记忆化(memoization)是一种构建函数的处理过程,能够记住上次计算结果,当函数计算得到结果时,就将该结果按照参数存储起来。

柯里化与反柯里化

柯里化,是一个逐步接收参数的过程。在接下来的剖析中,你会深刻体会到这一点。 反柯里化,是一个泛型化的过程。它使得被反柯里化的函数,可以接收更多参数。目的是创建一个更普适性的函数,可以被不同的对象使用。

js中减少使用不必要的if-else或switch_利用数组/对象代替if-else,switch

无论使用if-else,还是switch。当条件多的时候代码显得非常冗长,而且每次添加条件时需要修改主流程的代码,这样就破坏了类的开闭原则。为解决日后的维护可能存在问题,我们可以采用另一种比较优雅的实现方式来替换if-else,switch吗?