JavaScript排序算法（二）——归并排序

Edison 发布于2019-08-21 14:15 / 754人阅读

摘要：首先将数据集分解为一组只有一个元素的数组，然后通过创建一组左右子数组慢慢将它们合并起来，每次合并都保存一部分排好序的数据，最后这个数组排序完全。

基本思想

一个分治的策略，先进行划分，然后再进行合并
空间复杂度：nLogn

自顶向下的归并排序

采用递归的方式，方法比较简洁

function mergeSort(arr){
  // 设置终止的条件，
  if (arr.length < 2) {
    return arr;
  }
  //设立中间值
  var middle = parseInt(arr.length / 2);
  //第1个和middle个之间为左子列
  var left = arr.slice(0, middle);
  //第middle+1到最后为右子列
  var right = arr.slice(middle);
  if(left=="undefined"&&right=="undefined"){
     return false;
  }
  return merge(mergeSort(left), mergeSort(right));
}

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

  while (left.length && right.length) {
    if(left[0] <= right[0]){
      //把left的左子树推出一个，然后push进result数组里
       result.push(left.shift());
    }else{
      //把right的右子树推出一个，然后push进result数组里
     result.push(right.shift());
    }
  }
  //经过上面一次循环，只能左子列或右子列一个不为空，或者都为空
  while (left.length){
    result.push(left.shift());
  } 
  while (right.length){
    result.push(right.shift());
  }
  return result;
}
// 测试数据
var nums=[6,10,1,9,4,8,2,7,3,5]；
mergeSort(nums);

自底向上的归并排序

递归的深度太深，使用一种非递归的方式。首先将数据集分解为一组只有一个元素的数组，然后通过创建一组左右子数组慢慢将它们合并起来，
每次合并都保存一部分排好序的数据，最后这个数组排序完全。

function mergeSort(arr){
  if(arr.length<2){
    return;
  }
  //设置子序列的大小
  var step=1; 
  var left,right;
  while(step
参考资料

Sorting Algorithms in Javascript

《Data Structures& Algorithms with JavaScript》Michael McMilan著

idc机房托管超融合服务器归并排序算法归并排序二路归并排序 java归并排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/87832.html

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
JavaScript 排序算法图解（JavaScript sorting algorithms）

摘要：基础构造函数以下几种排序算法做为方法放在构造函数里。代码图解选择排序选择排序算法是一种原址比较排序算法。它的性能通常比其他的复杂度为的排序算法要好。代码划分过程图解排序没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。基础构造函数以下几种排序算法做为方法放在构造函数里。 function ArrayList () { var array = []; // 交换位置...

h9911 2019-08-21 12:04 评论0 收藏0
JS数据结构与算法_排序和搜索算法

摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。上一篇：JS数据结构与算法_树写在前面这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...

姘搁『 2019-08-23 16:26 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

caoym 2019-07-31 10:56 评论0 收藏0