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) {
   //下面是對本次的所有分組做直接插入排序
   for(int i=val; i<len; i++) {
    int temp = arr[i];
    /*
     * 為什么每次都用temp比較呢？
     * 因為直接插入就是找到temp的合適位置。
     * 為什么temp<arr[j-val]這個條件可以放在for內呢？
     * 因為原來的組內數據已經有序，找到位置就停止便是。
     * 不甚理解的去看直接插入排序吧。
     */
    for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
     /*
      * 為什么是arr[j-val]不是arr[j]呢？
      * 因為j=i開始的，而且條件是j>=val&&temp<arr[j-val]
      */
     arr[j] = arr[j-val];
    }
    /*
     * 注意不是arr[i] = temp
     * 直接插入排序也是這樣的。
     * 為什么呢？
     * 因為j是位置，i是待插入元素
     */
    arr[j] = temp;
   }
  }
 }
}