希尔排序

    /**
     * 的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
     * @param args
     */
    
    public static void main(String[] args) {
    
        int arr[] ={75,70,85,80,60,100,90};
        ShellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    
    
    public static  int[] ShellSort( int[] arr){
        //int arr[] ={75,70,85,80,60,100,90};
       // int grow= arr.length/2;
        int grow= arr.length/2;
        while(grow>=1){
            for(int i =grow; i<arr.length ;i++){
    
                int insertValue =arr[i];
    
                // 插入的位置
                int insertIndex=i-grow;
                while( insertIndex >=0 && insertValue < arr[insertIndex]){
                    //待插入的值比已排序部分的元素值小,已排序部分当前比较元素后移
                    arr[insertIndex+grow] =arr[insertIndex];
                    //待插入的值比已排序部分的元素值小，插入位置前移
                    insertIndex= insertIndex -grow;
                }
                //则将待插入的值赋值到对应位置的数组中
                arr[insertIndex+grow] = insertValue;
            }
            grow=grow/2;
        }
    
        return arr;
    }