使用Java实现希尔排序算法的简单示例
简介
希尔排序(缩小增量法)属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
h=3*h+1
反过来程序需要反向计算h序列，应该使用
h=(h-1)/3
代码实现
实现代码1：
publicstaticvoidshellSort(int[]arr){
inttemp;
for(intdelta=arr.length/2;delta>=1;delta/=2){//对每个增量进行一次排序
for(inti=delta;i<arr.length;i++){
for(intj=i;j>=delta&&arr[j]<arr[j-delta];j-=delta){//注意每个地方增量和差值都是delta
temp=arr[j-delta];
arr[j-delta]=arr[j];
arr[j]=temp;
}
}//loopi
}//loopdelta
}
实现代码2：
publicstaticvoidshellSort2(int[]arr){
intdelta=1;
while(delta<arr.length/3){//generatedelta
delta=delta*3+1;//<O(n^(3/2))byKnuth,1973>:1,4,13,40,121,...
}
inttemp;
for(;delta>=1;delta/=3){
for(inti=delta;i<arr.length;i++){
for(intj=i;j>=delta&&arr[j]<arr[j-delta];j-=delta){
temp=arr[j-delta];
arr[j-delta]=arr[j];
arr[j]=temp;
}
}//loopi
}//loopdelta
}
上面程序在和直接插入法比较，会发现其与直接插入排序的差别在于：直接插入排序中的h会以1代替。
Shell排序是不稳定的，它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间。