高级排序之归并排序、希尔排序

高级排序之归并排序、希尔排序

前言

继上次排序算法简单排序算法之冒泡、插入和选择排序-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增量排序。

高级排序之归并排序、希尔排序

注意:此图演示的是4,2,1增量

如何设置算法的增量值

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

h

3*h+1

(h-1)/3

1

4

4

13

1

13

40

4

40

121

13

121

364

40

364

1093

121

1093

3280

364

明显的,这个增量值不能大于待排序的数组长度,比如待排序数组长度是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的个人技术博客

本文来自投稿,不代表重蔚自留地立场,如若转载,请注明出处https://www.cwhello.com/52411.html

如有侵犯您的合法权益请发邮件951076433@qq.com联系删除

(0)
人生就是一场修行321人生就是一场修行321订阅用户
上一篇 2022年8月8日 11:34
下一篇 2022年8月8日

相关推荐

联系我们

QQ:951076433

在线咨询:点击这里给我发消息邮件:951076433@qq.com工作时间:周一至周五,9:30-18:30,节假日休息