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

　　前言
　　继上次排序算法简单排序算法之冒泡、插入和选择排序Java实现版后，本文学习高级排序算法归并排序、希尔排序，快速排序将在后续更新。
　　本文实现代码调用方法，部分来自前一个文章：简单排序算法之冒泡、插入和选择排序Java实现版归并排序
　　归并排序的思想是把一个数组分成两半，然后对每一个二分支一划分成两个4分之一，以此类推，直到子数组只含有一个数据项为止，然后对每对划分结果进行合并排序。具体图示如下：
　　代码实现privatestaticvoidmerge（int〔〕array，int〔〕workSpace，intlowPtr，inthighPtr，intupperBound）｛intj0；intlowerBoundlowPtr；intmidhighPtr1；intnupperBoundlowerBound1；while（lowPtrmidhighPtrupperBound）｛if（compare（array〔lowPtr〕，array〔highPtr〕）0）｛copyData（array〔lowPtr〕，j，workSpace）；｝else｛copyData（array〔highPtr〕，j，workSpace）；｝｝while（lowPtrmid）｛copyData（array〔lowPtr〕，j，workSpace）；｝while（highPtrupperBound）｛copyData（array〔highPtr〕，j，workSpace）；｝for（j0；jn；j）｛copyData（workSpace〔j〕，lowerBoundj，array）；｝｝privatestaticvoidrecMergeSort（int〔〕array，int〔〕workSpace，intlowerBound，intupperBound）｛if（lowerBoundupperBound）｛return；｝intmid（lowerBoundupperBound）2；recMergeSort（array，workSpace，lowerBound，mid）；分割左侧recMergeSort（array，workSpace，mid1，upperBound）；分割右侧merge（array，workSpace，lowerBound，mid1，upperBound）；合并排序｝合并排序paramarraypublicstaticvoidmergeSort（int〔〕array）｛compareCount0；swapCount0；int〔〕workspacenewint〔array。length〕；longstartnewDate（）。getTime（）；recMergeSort（array，workspace，0，array。length1）；longendnewDate（）。getTime（）；printResult（归并排序，复制次数，start，end）；｝执行结果
　　冒泡排序比较次数：49995000，交换次数：24677093，耗时：167毫秒
　　选择排序比较次数：49995000，交换次数：9996，耗时：68毫秒
　　插入排序比较次数：25187177，复制次数：25187284，耗时：33毫秒
　　归并排序比较次数：120284，复制次数：267232，耗时：3毫秒
　　从结果可以看出归并排序比简单排序的任何一个算法都要快，但它要多耗费一倍的存储空间。（归并排序算法的排序速度是相当快的，但也存在非常显著的缺点，就是它对存储空间的过多占用）希尔排序
　　希尔排序是基于插入排序的，它的发明者DonaldL。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有序，然后在m1比01（即比较项位置右移一位），直到所有数据都完成了m增量排序为止，此时就形成了m增量的基本有序，对于大量数据排序，也应该使用大增量值开始，然后逐渐缩小增量，最后可以直接使用插入排序对基本有序的数据进行排序了（插入排序对基本有序的数据排序是非常快的）。普通的排序可以看成是1增量排序。
　　注意：此图演示的是4，2，1增量如何设置算法的增量值
　　这里使用Knuth提出的公式：h3h1来计算合适的第一次增量值，然后用h（h1）3逐级计算缩小的增量值。
　　h
　　3h1
　　（h1）3
　　1hr4hr4hr13hr1hr13hr40hr4hr40hr121hr13hr121hr364hr40hr364hr1093hr121hr1093hr3280hr364hr明显的，这个增量值不能大于待排序的数组长度，比如待排序数组长度是1000，则第一次增量值应该是364，然后用公式（h1）3计算下一次的增量值为121，再下一次则为40，最终为1（因为最终都要对基本有序的序列做一次普通的插入排序（1增量））。代码实现希尔排序paramarraypublicstaticvoidxierSort（int〔〕array）｛compareCount0；swapCount0；intinner，outer；inttemp；inth1；计算跨度while（harray。length3）｛hh31；｝longstartnewDate（）。getTime（）；while（h0）｛for（outerh；outerh1compare（array〔innerh〕，temp）0）｛copy（innerh，inner，array）；innerh；｝copyData（temp，inner，array）；｝h（h1）3；｝longendnewDate（）。getTime（）；printResult（希尔排序，复制次数，start，end）；｝执行结果
　　冒泡排序比较次数：49995000，交换次数：49502991，耗时：103毫秒
　　选择排序比较次数：49995000，交换次数：9901，耗时：70毫秒
　　插入排序比较次数：24574076，复制次数：24573983，耗时：42毫秒
　　归并排序比较次数：120141，复制次数：267232，耗时：3毫秒
　　希尔排序比较次数：843997，复制次数：848708，耗时：11毫秒
　　从结果可以看出，希尔排序通过对插入排序增量的调整，有效减少了比较、复制的次数，很明显的提升了插入排序的排序效率。如你所见，希尔排序实现简单，效率高，所以几乎很多排序需求都可以从希尔排序开始评估最优排序算法。
　　至此，本文结束
　　原文格式更佳高级排序之归并排序、希尔排序NGUP的个人技术博客