前言

继上次排序算法简单排序算法之冒泡、插入和选择排序-Java实现版后，本文学习高级排序算法——归并排序、希尔排序，快速排序将在后续更新。

本文实现代码调用方法，部分来自前一个文章：简单排序算法之冒泡、插入和选择排序-Java实现版

归并排序

归并排序的思想是把一个数组分成两半，然后对每一个二分支一划分成两个4分之一，以此类推，直到子数组只含有一个数据项为止，然后对每对划分结果进行合并排序。具体图示如下：

代码实现

private static void merge(int[] array, int[] workSpace, int lowPtr, int highPtr, int upperBound) {
  int j = 0;
  int lowerBound = lowPtr;
  int mid = highPtr - 1;
  int n = upperBound - lowerBound + 1;

  while (lowPtr <= mid && highPtr <= upperBound) {
    if (compare(array[lowPtr],array[highPtr])<0) {
      copyData(array[lowPtr++],j++,workSpace);
    } else {
      copyData(array[highPtr++],j++,workSpace);
    }
  }
  while (lowPtr <= mid) {
    copyData(array[lowPtr++],j++,workSpace);
  }
  while (highPtr <= upperBound) {
    copyData(array[highPtr++],j++,workSpace);
  }
  for (j = 0; j < n; j++) {
    copyData(workSpace[j],lowerBound+j,array);
  }
}
private static void recMergeSort(int[] array,int[] workSpace, int lowerBound, int upperBound) {
  if (lowerBound == upperBound) {
    return;
  }
  int mid = (lowerBound + upperBound) / 2;
  recMergeSort(array,workSpace, lowerBound, mid); // 分割左侧
  recMergeSort(array,workSpace, mid + 1, upperBound); // 分割右侧

  merge(array,workSpace,lowerBound,mid+1,upperBound); // 合并排序
}

/**
 * 合并排序
 * @param array
 */
public static void mergeSort(int[] array){
  compareCount=0;
  swapCount=0;
  int[] workspace = new int[array.length];
  long start = new Date().getTime();
  recMergeSort(array,workspace,0,array.length-1);
  long end = new Date().getTime();
  printResult("归并排序","复制次数",start,end);
}

执行结果

冒泡排序——比较次数:49995000,交换次数:24677093,耗时:167毫秒

选择排序——比较次数:49995000,交换次数:9996,耗时:68毫秒

插入排序——比较次数:25187177,复制次数:25187284,耗时:33毫秒

归并排序——比较次数:120284,复制次数:267232,耗时:3毫秒

从结果可以看出归并排序比简单排序的任何一个算法都要快，但它要多耗费一倍的存储空间。(归并排序算法的排序速度是相当快的，但也存在非常显著的缺点，就是它对存储空间的过多占用)

希尔排序

希尔排序是基于插入排序的，它的发明者Donald L. Shell对插入排序做了一些调整，就大幅度的减少了插入排序所必需的工作量，我们先看一下希尔排序对插入排序做了那些调整。

插入排序通过1号位置与0号位置比对，将小的一方挪到左侧，然后2比1，复制（1）、3比2，复制多于（1）、4比3...逐步形成左侧“基本有序”，但也正是因为“2比1，3比2，4比3”导致复制次数逐渐增多。

而希尔排序则不是1比0、2比1、3比2了，它是计算出一个增量m，然后让m比0,2m比m,3m比2m，这就使m,2m,3m有序，然后在m+1比0+1（即比较项位置右移一位），直到所有数据都完成了m增量排序为止，此时就形成了m增量的基本有序，对于大量数据排序，也应该使用大增量值开始，然后逐渐缩小增量，最后可以直接使用插入排序对基本有序的数据进行排序了（插入排序对基本有序的数据排序是非常快的）。普通的排序可以看成是1增量排序。

如何设置算法的增量值

这里使用Knuth提出的公式：h=3*h+1 来计算合适的第一次增量值，然后用h=(h-1)/3逐级计算缩小的增量值。

明显的，这个增量值不能大于待排序的数组长度，比如待排序数组长度是1000，则第一次增量值应该是364，然后用公式(h-1)/3计算下一次的增量值为121,再下一次则为40，最终为1（因为最终都要对基本有序的序列做一次普通的插入排序（1增量））。

代码实现

/**
 * 希尔排序
 * @param array
 */
public static void xierSort(int[] array){
  compareCount=0;
  swapCount=0;

  int inner,outer;
  int temp;
  int h=1;
  // 计算跨度
  while(h<=array.length/3){
    h=h*3+1;
  }
  long start = new Date().getTime();
  while(h>0){
    for(outer=h;outer<array.length;outer++){
      temp = array[outer];
      inner = outer;
      while(inner>h-1 && compare(array[inner-h],temp)>0){
        copy(inner-h,inner,array);
        inner -= h;
      }
      copyData(temp,inner,array);
    }
    h=(h-1)/3;
  }
  long end = new Date().getTime();
  printResult("希尔排序","复制次数",start,end);
}

执行结果

冒泡排序——比较次数:49995000,交换次数:49502991,耗时:103毫秒

选择排序——比较次数:49995000,交换次数:9901,耗时:70毫秒

插入排序——比较次数:24574076,复制次数:24573983,耗时:42毫秒

归并排序——比较次数:120141,复制次数:267232,耗时:3毫秒

希尔排序——比较次数:843997,复制次数:848708,耗时:11毫秒

从结果可以看出，希尔排序通过对插入排序 增量的调整，有效减少了比较、复制的次数，很明显的提升了插入排序的排序效率。如你所见，希尔排序实现简单，效率高，所以几乎很多排序需求都可以从希尔排序开始评估最优排序算法。

至此，本文结束

原文格式更佳 高级排序之归并排序、希尔排序|NGUP的个人技术博客