希尔排序（Shell Sort）是插入排序的一种，也是直接插入排序的更高效的改进版本，希尔排序充分利用了插入排序的两个特点：
1）当数据规模小的时候非常高效。
2）当给定数据已经有序时的时间复杂度为O(n)。
所以，Shell排序每次把数据分成若干块，来使用插入排序，而且之后在这若干个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停地合并小块，直到最后一个小块。
这里每次分成若干个小块是通过“增量”来控制的，开始的时候增量较大，接近n/2，从而使得分割出来接近n/2个小块，逐渐的减小“增量”，最终减小到1。
例如：
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//计算出最大的h值inth=1;while(h<=data.length/3){h=h*3+1;}while(h>0){for(inti=h;i<data.length;i+=h){if(data[i]<data[i-h]){inttmp=data[i];intj=i-h;while(j>=0&&data[j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//计算出下一个h值h=(h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t);}System.out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(data);shellSort(data);print(data);}}运行结果如下：
461958146958145698145689145689