前言
继上次排序算法简单排序算法之冒泡、插入和选择排序-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联系删除