七大排序之希尔排序

时间复杂度： ~

空间复杂度：

稳定性：不稳定

1、基本思想

   希尔排序是插入排序的一种，又称为缩小增量法。其思想就是先选定一个整数 gap ，把待排序数组中间隔为 gap 的数分为一组，并对每一组内的数进行插入排序。然后，取，重复上述分组排序工作。当 gap = 1时，所有数在同一组内排好序。

2、代码讲解和实现

希尔排序实现可以分为两步：

       1：分组

       2：组内排序

① 分组

       我们首先要给 gap 取值，通常 会把数组的长度先赋值给 gap，然后以gap为步长进行分组排序。接着 gap除以2，再进行上述操作。

       最后 我们一定要把数组作为一个整体再进行排序，因为每次分组就肯能落下几个数，所以最后gap 一定要赋值为1。

② 组内排序

       组内排序跟插入排序大致相同，在插入排序中外循环是从 1下标开始进行插入，而在希尔排序中 gap 是不断变化的，所以外循环要从 gap 为下标开始，每次++，争取把每个组都遍历到。

       内循环 j 从 i - gap 开始，每次减去 gap，这样一组内的元素都趋于有序了。

 //组内插入排序
    private static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    //分组
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);//把数组作为一个整体进行排序

3、特性总结

1.希尔排序是对直接插入排序的优化。

2.当gap > 1 时都是预排序，目的是让数组更接近有序。当 gap == 1 时，数组已经接近有序，这样就会很快。这样整体而言，可以达到优化的效果。

3.希尔排序的时间复杂度不好算，因为gap的取值方法很多，导致很难去计算，因此在很多书中给出的希尔排序时间复杂度都不固定。我们可以暂时按照 ~ 来算。

  4.希尔排序不是稳定的排序。