排序效率对比-插入排序vs希尔排序
对于几十个或者几千个整数进行排序，各种算法程序执行时间没什么差别，但如果要对几十万，几百万或者更多的整数排序，那么就要精心挑选设计一些算法。
看一个例子：
对20万个整数进行排序，一种算法实现如下：
public static <T extends Comparable<? super T>> void insertionSort(T[] a) {if (null == a) {return ;}int j ;for ( int p = 1 ; p < a.length ; p++) {T tmp = a[p] ;for ( j = p ; j > 0 && tmp.compareTo(a[j-1]) < 0 ; j--) {a[j] = a[j-1] ;}a[j] = tmp ;}}
以上是最基本的插入排序算法：
执行时间 耗时：61秒，1分钟左右
现在增加整数数量，对50万个整数进行排序
执行时间 变成了耗时：557秒 大约需要漫长的10分钟
现在看另外一种算法：
public static <T extends Comparable<? super T>> void shellSort(T[] a) {if (null == a) {return ;}int j ;for (int gap = a.length ; gap > 0 ; gap/=2) {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 ;}}}
以上是希尔排序算法，
先看看同样是对20万个整数排序：
执行时间 耗时：126毫秒 大概0.1秒
再对50万个整数排序
执行时间 耗时：380毫秒 大概0.4秒
效率大概比插入排序有5500倍的提升
希尔排序发明者是Donald Shell,于1959年提出，该算法是冲破二次时间屏障的第一批算法之一，不过直到它最初被发现的若干年后才证明了它的二次时间界
原始论文是 D.L.Shell,"A High-Speed Sorting Procedure" Communications of the ACM, 2(1959),30-32