public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};
System.out.print("排序前：");
for(int o: arr) {
System.out.print(o+" ");
}
System.out.println();
shellSort(arr);
System.out.print("排序后：");
for(int o: arr) {
System.out.print(o+" ");
}
System.out.println();
}
private static void shellSort(int[] arr) {
int j;
int len = arr.length;
for(int val=len>>1; val>0; val>>=1) {
//下面是對(duì)本次的所有分組做直接插入排序
for(int i=val; i<len; i++) {
int temp = arr[i];
/*
* 為什么每次都用temp比較呢？
* 因?yàn)橹苯硬迦刖褪钦业絫emp的合適位置。
* 為什么temp<arr[j-val]這個(gè)條件可以放在for內(nèi)呢？
* 因?yàn)樵瓉淼慕M內(nèi)數(shù)據(jù)已經(jīng)有序，找到位置就停止便是。
* 不甚理解的去看直接插入排序吧。
*/
for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
/*
* 為什么是arr[j-val]不是arr[j]呢？
* 因?yàn)閖=i開始的，而且條件是j>=val&&temp<arr[j-val]
*/
arr[j] = arr[j-val];
}
/*
* 注意不是arr[i] = temp
* 直接插入排序也是這樣的。
* 為什么呢？
* 因?yàn)閖是位置，i是待插入元素
*/
arr[j] = temp;
}
}
}
}
