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

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

 

Web Worker 详细介绍_Web Workers的使用

web worker 是运行在后台的 JavaScript,独立于其他脚本,也就是说在Javascript单线程执行的基础上,开启一个子线程,进行程序处理,而不影响主线程的执行。Service Worker 是一个由事件驱动的 worker,它由源和路径组成,以加载 .js 文件的方式实现的。

数字在JavaScript中是如何编译的

JavaScript中的所有数字都是浮点数。这篇博客文章解释了这些浮点数如何在64位二进制内部表示。浮点数并不一定等于小数,定点数也并不一定就是整数。所谓浮点数就是小数点在逻辑上是不固定的,而定点数只能表示小数点固定的数值

window.location.href的用法(动态输出跳转)

javascript中的location.href有很多种用法,window.location.href 语句可以实现一个框架的页面在执行服务器端代码后刷新另一个框架的页面

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

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

js秒数转换成时分秒_js如何将秒拼接为时分秒显示?

接口返回的是int类型的秒数,在前端显示要求拼接为时分秒显示,这篇文章主要讲解实现js秒数转换成时分秒的方法。

JavaScript中变量提升和函数提升的意义理解

在ES6之前,Js中是没有块级作用域的,只存在全局作用域和函数作用域。变量提升即将变量声明提升到它所在作用域的最开始的部分;函数提升只有函数声明中才发生。

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

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

基于规则评分的密码强度检测算法分析及实现(JavaScript)

用正则表达式做用户密码强度的通过性判定,过于简单粗暴,不但用户体验差,而且用户帐号安全性也差。那么如何准确评价用户密码的强度,保护用户帐号安全呢?本文分析介绍了几种基于规则评分的密码强度检测算法

js设备判断_判断移动端还是PC端?判断android还是ios?判断移动端浏览器类型?

js判断用户的浏览设备是移动设备还是PC?判断详细浏览器设备信息。判断微信、新浪、QQ打开。判断是android系统还是ios系统...

javascript中关键词in用法介绍【js 关键字 in 的使用方法】

js中关键词...in... 从字面上理解就是什么在什么中,在js中差不多也是表达这个意思,主要作用:1用于数组和对象的判断、2 遍历数组或者对象