希尔排序思想：使数组中随意间隔为h的元素都是有序的。
希尔排序是插入排序的优化。先对数组局部进行排序，最后再使用插入排序将部分有序的数组排序。
代码例如以下：
/*** * @author seabear**/public class ShellSort {public static void sort(Comparable[] a){int N = a.length;int h = 1;while(h < N/2){h = 4 * h + 1;}while(h >= 1){for(int i = h; i < N; i++){for(int j = i; j >= h && less(a[j],a[j-h]); j -= h){int n = j - h;System.out.println(j + ":" + a[j] + "," + n + ":" + a[j-h]);exch(a,j,j-h);show(a);}}h = h / 4;}}public static boolean less(Comparable v,Comparable w){return v.compareTo(w) < 0;}public static void exch(Comparable[] a,int i,int j){Comparable temp = a[i];a[i] = a[j];a[j] = temp;}public static boolean isSort(Comparable[] a){for(int i = 1; i < a.length; i++){if(less(a[i],a[i-1])){return false;}}return true;}public static void show(Comparable[] a){for(int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}System.out.println();}public static void main(String[] args){Integer[] a = new Integer[10];for(int i = 0; i < 10; i++){a[i] = (int)(Math.random() * 10 + 1);System.out.print(a[i] + " ");}System.out.println();sort(a);show(a);}
}