希尔排序在不同增量序列下的效率差异
在上一篇中，看到了在对50万个整数排序时，希尔排序的巨大效率优势。
上篇文章中希尔排序采用的增量序列是希尔排序的发明人 Shell建议的序列
Tip: 什么是增量序列？
序列 h1, h2, ..., ht, 叫做增量序列（increment sequence）只要h1=1 任何增量序列都是可行的，不过，有些增量序列比另外一些增量序列效率更高在使用增量h(k)的一趟排序之后，对于每一个i，都有a[i] <= a[i+h(k)]，所有间隔h(k)的元素都被排序，此时称是h(k)排序的(h(k)-sorted)例如 有一组需要排序的9个整数：29, 16, 12, 9, 8, 20, 30, 25, 11假如 增长序列为:1, 3, 5那么h(2) 为 3使用h(2) 的一趟排序之后的结果(对位置间隔为3的整数进行排序)：(a[0]<=a[0+3], a[1]<=a[1+3], a[2]<=a[2+3]...)9, 8, 11, 29, 16, 12, 30, 25, 20可以看出，位置间隔为3的整数都是排好序的
Shell建议的序列: h(t)=[N/2] N为需要排序的整数数量, h(k) = [h(k+1)/2]，上篇文章中用到的就是这个序列。
希尔增量的问题在于，这些增量未必是互为素数的，因此较小的增量可能影响很小。Hibbard于1963年提出一个稍微不同的增量序列(详情见论文：Thomas.H.Hibbard, "An Empirical Study of Minimal Storage Sorting" Communications of the ACM, 6(1963),206-213)
《An Empirical Study of Minimal Storage Sorting》 https://dl.acm.org/doi/10.1145/366552.366557
使用Hibbard的增量序列实现：
public static <T extends Comparable<? super T>> void shellSortHibbard(T[] a) {if (null == a) {return ;}int j ;for (int k = log2(a.length) ; k > 0 ; k--) {int gap = (1<<k)-1 ;// log.info(" k={}, gap = {}", k, gap);for (int i = gap ; i < a.length ; i++) {T tmp = a[i] ;for (j = i ; j >= gap && tmp.compareTo(a[j-gap])<0 ; j-=gap) {a[j] = a[j-gap] ;}a[j] = tmp ;}}}public static int log2(int N) {double rst = Math.log(N)/Math.log(2);//Math.log的底为ereturn (int)rst ;}
现在对1亿个随机整数用希尔排序进行排序，采用两种增量序列来看看效率差异：
使用Shell增量序列：
[1]: gap=50000000[2]: gap=25000000[3]: gap=12500000[4]: gap=6250000[5]: gap=3125000[6]: gap=1562500[7]: gap=781250[8]: gap=390625[9]: gap=195312[10]: gap=97656[11]: gap=48828[12]: gap=24414[13]: gap=12207[14]: gap=6103[15]: gap=3051[16]: gap=1525[17]: gap=762[18]: gap=381[19]: gap=190[20]: gap=95[21]: gap=47[22]: gap=23[23]: gap=11[24]: gap=5[25]: gap=2[26]: gap=1
程序执行一共耗时：567(秒)
使用Hibbard增量序列排序：
k=26, gap = 67108863k=25, gap = 33554431k=24, gap = 16777215k=23, gap = 8388607k=22, gap = 4194303k=21, gap = 2097151k=20, gap = 1048575k=19, gap = 524287k=18, gap = 262143k=17, gap = 131071k=16, gap = 65535k=15, gap = 32767k=14, gap = 16383k=13, gap = 8191k=12, gap = 4095k=11, gap = 2047k=10, gap = 1023k=9, gap = 511k=8, gap = 255k=7, gap = 127k=6, gap = 63k=5, gap = 31k=4, gap = 15k=3, gap = 7k=2, gap = 3k=1, gap = 1
程序执行一共耗时：523(秒)。
看的出来，同样是希尔排序，对一亿个随机整数排序使用Hibbard增量序列比使用Shell增量序列节省43秒时间。
还有一种增量序列，比Hibbard序列效率还要高，而且高出一倍，能够让希尔排序对一亿个整数排序时时间缩短到259秒
性能几乎提升一倍，感兴趣的读者可以留言索取最佳效率的增量序列