插入排序之希尔排序

原文地址https://blog.csdn.net/qq_39207948/article/details/80006224
1、何为希尔排序？
就是先把这一组数按照取半分组，就是每隔总长度的一半就分组。然后把同一组里面的数进行插入排序。然后再按刚刚取半的一半分组，再次组内插入排序，以此类推，直到这个取半数字为1时，进行整个插入排序，因为这时候基本上都是有序的，而插入排序顺序越整齐，速度越快，这样对减少时间复杂度。
因为长度越短的插入排序，时间越短。两个4就比一个8时间短，4的最坏比较次数的每次都比，为3+2+1，8：7+...+1=28,显然2*6<28。
2、图解

图片来自网络
3、代码演示

 public static int[] sort(int arr[]){
        //取半数为每次的逻辑分组规则
        for(int gep=arr.length/2;gep>0;gep/=2){
            //对每组数的第二个开始进行插入排序
            for(int i=gep;i<arr.length;i++){
                arr=insert(arr,i,gep);
            }
        }
        return arr;
    }

    private static int[] insert(int[] arr, int i, int gep) {
        //传进来排序的值
        int inserted=arr[i];
        //最后结束for要把要排序的值放到与这个索引有关的位置
        int j;
        //前一个大于要插入的，就要把前一个给后一个
        for(j=i-gep;j>=0 && arr[j]>inserted;j-=gep){
            arr[j+gep]=arr[j];
        }
        //for循环之后。j又-gep，所以想得到最后一次的索引，要把它加回来
        arr[j+gep]=inserted;
        return arr;
    }

4、时间复杂度
以当前取半来说，
最好时间复杂度为O(logn[n-logn])=O(nlogn)
最坏时间复杂度为O(logn[n-logn]·n/logn)=O(n²)
但是如果不是取半的话，“
Hibbard提出了另一个增量序列{1,3,7，...,2^{k-1}，这种序列的时间复杂度(最坏情形)为O(n}1.5)
Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,...}。”
5、空间复杂度O(1)
6、稳定性：不稳定
因为分组时可能把相等的数中以前在后面的移到前面去

图片来自网络