背景

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

先分组再排序

package top.ltyzqhh.Annotation;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] a={324,234,532,1313,1,3,553};
        System.out.println(Arrays.toString(a));
        shellSort(a);
        System.out.println(Arrays.toString(a));
    }

  /*  public static void insertionSort(int[] array){
        //外层循环，判断我们这个要走多少次；
        for (int i = 1; i <array.length; i++) {
            int temp=array[i];
            int tempindex=i;
            //内层循环，判断如果这个数比前一个小的话则交换直到不能交换为止
            // 这个tempindex-1>=0条件要先于temp<array[tempindex-1]，不然会先执行temp<array[tempindex-1]，导致坐标越界
            while( tempindex-1>=0 && temp<array[tempindex-1] ){
                array[tempindex]=array[tempindex-1];
                tempindex--;
            }
            array[tempindex] =temp;
        }

    }*/

    public static void shellSort(int[] array){
        //步长
        for (int step= array.length/2 ; step >0 ; step/=2) {
            for (int i=step;i<array.length;i++) {
                int insertIndex =i;
                int insertValue=array[i];
                while( insertIndex-step>=0 && insertValue<array[insertIndex-step] ){
                    array[insertIndex]=array[insertIndex-step];
                    insertIndex-=step;
                }
                array[insertIndex] =insertValue;

            }
        }
    }
}