算法之归并排序

概念

归并排序(Merge-Sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

关于分治法:

分治法可以通俗的解释为:把一片领土分解,分解为若干块小部分,然后一块块地占领征服,被分解的可以是不同的政治派别或是其他什么,然后让他们彼此异化。

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题。对于一个规模为n的问题,若n很小则可以直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。(摘录自百科)

以下将介绍的主要是二路归并。用一张图描述归并的过程,如下:

二路归并的空间复杂度为: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);

在递归过程中,使用了0.5nlgn-nlgn次数的比较。因此其空间复杂度为n*log(n)

自底向上的归并排序

这是一种非递归的方式。
首先将数据分解为一组只有一个元素的数组,然后通过创建一组左右子数组慢慢将它们合并起来,每次合并都保存一部分排好序的数据,最后这个数组排序完全。思路与上图的合并过程类似。

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);

从空间复杂度来看,与自顶向下的复杂度一样。
而实际使用中,长度为100左右数据做对比,自底而上的排序执行速度快一些,原因呢?相同的数据对比过程中,自顶而下的比较次数会更多一些。

针对自顶而下的归并算法还可以进行优化,想进行深入探究可以查看这里

参考

Ref
推荐书籍《Data Structures& Algorithms with JavaScript》- Michael McMilan

发表评论

电子邮件地址不会被公开。 必填项已用*标注