希尔排序分析：假设数组array有array.length=N个元素，array.length是偶数也好，奇数也行，需要log2(N)趟分区，最后一趟只有1个区，区元素间隔1，如果N是奇数，那么之前不计入每一趟分区区块记录的数在最后一趟分区加入区块中进行插入排序。
第1趟分区：分得 N/2^1个区，区里边的元素下标间隔 N/2^1,每个区里边的元素有 2^1个。
此时第1个区到第N/2^1个区中，每个区里边都只需要走一趟，一次比较。
...
第i趟分区：分得 N/2^i 个区，区里边的元素下标间隔 N/2^i,每个区里边的元素有 2^i个。
此时第1个区到第N/2^i个区中，每个区里面需要比较走2^i-1趟，
其中每一趟的比较次数不确定
...
第log2(N)趟分区（最后一次分区）：分得 N/2^(log2(N))=1 个区,区元素间隔1，区里面的元素2^(log2(N))即N个，插入排序走N-1趟，每趟比较次数不确定
时间复杂度：O(n^(3/2)),需要一个额外空间O(1)。
我个人对希尔排序的理解代码：
public class ShellSortMy {
public static void shellSortMy(int[] array) {
int jump=array.length/2;
while(jump!=0) {//共多少趟
int i,j,k,l,temp=0;
for(k=0,l=jump;k<jump;k++,l++) {//每趟多少区块，k记录每趟分区得到的区块数,l记录区元素间隔
for(i=l;i<array.length;i=i+jump) {//每趟各个区块依此独立插入排序
temp=array[i];
j=i-jump;
while(j>=0&&array[j]>temp) {//每趟分区中各区块每趟后数与前数组比较次数
array[j+jump]=array[j];
j=j-jump;
}
array[j+jump]=temp;
}
}
jump=jump/2;
}
}
public static void main(String[] args) {
int[] array= {6,5,3,2,4,8,9,1};// TODO Auto-generated method stub
System.out.println("排序前：");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
shellSortMy(array);
System.out.println("排序后:");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
}
输出结果：
排序前：
6 5 3 2 4 8 9 1
排序后:
1 2 3 4 5 6 8 9
一般理解：
public class ShellSortBook {
public static void shellSortBook(int[] array) {
int jump=array.length/2;
while(jump!=0) {
int i,j,temp=0;
for(i=jump;i<array.length;i++) {
temp=array[i];
j=i-jump;
while(j>=0&&array[j]>temp) {
array[j+jump]=array[j];
j=j-jump;
}
array[j+jump]=temp;
}
jump=jump/2;
}
}
public static void main(String[] args) {
int[] array= {6,5,3,2,4,8,9,1};// TODO Auto-generated method stub
System.out.println("排序前：");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
shellSortBook(array);
System.out.println("排序后:");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
}
输出结果：
排序前：
6 5 3 2 4 8 9 1
排序后:
1 2 3 4 5 6 8 9