概述
希尔排序是直接插入排序的改进，是一种非稳定排序。
通过加大排序的间隔，并让相隔这个"间隔"的子序列进行插入排序。当排序完一趟后，通过减小数据项的"间隔"依次排序下去。
java代码
public class ShellSort {
public static void main(String[] args) {
int[] array = {98,21,62,48,33,6,55,17};
System.out.print("ShellSort\n");
printArray(array);
System.out.print("start:\n");
shellSort(array);
System.out.print("end:\n");
}
static void shellSort(int[] arr){
int increment = arr.length;
while (true){
increment = increment/3+1;
for(int i=0;i<increment;i++){//分组
//对分组进行插入排序
for(int j=i+increment;j<arr.length;j=j+increment){
int temp = arr[j];
for(int k = j-increment;k>=0;k=k-increment){
if(temp<arr[k]){
arr[k+increment] = arr[k];
arr[k] = temp;
}else{
arr[k+increment] = temp;
break;
}
}
}
printArray(arr);
}
if(increment==1){
break;
}
}
}
static void printArray(int[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.print("\n");
}
}
输出
ShellSort
98 21 62 48 33 6 55 17
start:
48 21 62 55 33 6 98 17
48 17 62 55 21 6 98 33
48 17 6 55 21 62 98 33
6 17 21 55 48 62 98 33
6 17 21 33 48 55 98 62
6 17 21 33 48 55 62 98
end:
通过代码发现，直接插入排序与希尔排序的区别就是数据项间隔为1.
时间复杂度
平均时间复杂度 : O(n1.25)
空间复杂度
没有分配额外空间，空间复杂度为O(1)。
