1:
　2:
　3:
　4:
　5:
　6:
　7:
　8:
　9:
 10:
 11:
 12:
 13:
 14:
 15:
 16:
 17:
 18:
 19:
 20:
 21:
 22:
 23:
 24:
 25:
 26:
 27:
 28:
 29:
 30:
 31:
 32:
 33:
 34:
 35:
 36:
 37:
 38:
 39:
 40:

class InsertSortTest{
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 5, 4, 9, 1, 3, 0, 7};
        
        System.out.print("ソート前：");
        arrayPrintln(arr);
        
        shellSort(arr);

        System.out.print("ソート後：");
        arrayPrintln(arr);
    }

    //シェルソート****************************************
    public static void shellSort(int[] arr){
        int i, j;
        for(int gap=arr.length / 2; gap > 0; gap/=2){
            for(int h=0; h<gap; h++){
                for(i=h+gap; i<arr.length; i+=gap){
                    int tmp = arr[i];
                    for(j=i-gap; j>=h; j-=gap){
                        if(arr[j] < tmp){
                            break;
                        }
                        arr[j+gap] = arr[j];
                    }
                    arr[j+gap] = tmp;
                }
            }
        }
    }
    
    //配列の値を出力するメソッド*******************
    public static void arrayPrintln(int[] arr){
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
}