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

基本思想

一个分治的策略，先进行划分，然后再进行合并
空间复杂度：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<arr.length){
    left=0;
    right=step;
    while(right+step<=arr.length){
      mergeArrays(arr,left,left+step,right,right+step);
      left=right+step;
      right=left+step;
    }
    if(right<arr.length){
      mergeArrays(arr,left,left+step,right,arr.length);
    }
    step*=2;
  }
}
//对左右序列进行排序
function mergeArrays(arr,startLeft,stopLeft,startRight,stopRight){
  // 建立一个左、右数组
  var rightArr=new Array(stopRight-startRight+1);
  var leftArr=new Array(stopLeft-startLeft+1);
  // 给右数组赋值
  k=startRight;
  for(var i=0;i<(rightArr.length-1);++i){
    rightArr[i]=arr[k];
    ++k;
  }
   // 给左数组赋值
  k=startLeft;
  for(var i=0;i<(leftArr.length-1);++i){
    leftArr[i]=arr[k];
    ++k;
  }
  //设置哨兵值，当左子列或右子列读取到最后一位时，即Infinity，可以让另一个剩下的列中的值直接插入到数组中
  rightArr[rightArr.length-1]=Infinity;
  leftArr[leftArr.length-1]=Infinity;
  var m=0;
  var n=0;
  // 比较左子列和右子列第一个值的大小，小的先填入数组，接着再进行比较
  for(var k=startLeft;k<stopRight;++k){
    if(leftArr[m]<=rightArr[n]){
      arr[k]=leftArr[m];
      m++; 
    }
    else{
      arr[k]=rightArr[n];
      n++;
    }
  }
}
// 测试数据
var nums=[6,10,1,9,4,8,2,7,3,5]；
mergeSort(nums);

参考资料

1. Sorting Algorithms in Javascript

2. 《Data Structures& Algorithms with JavaScript》Michael McMilan著