希尔排序

思想

通过比较相距一定间隔的元素来工作；各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
由于这个原因，希尔排序有时也叫作缩减增量排序

图片

代码

    public static <AnyType extends Comparable<? super AnyType>>
    void shellSort(AnyType[] a) {
        //1.定义指向序列最后那个，j-gap代开始那个
        int j;

        //2.循环多少躺，每次gap减半
        for (int gap = a.length / 2; gap > 0; gap /= 2) {
            //1.一次循环走一趟gap
            for (int i = gap; i < a.length; i++) {
                //1.定义一个临时变量指向序列最后那个
                AnyType tmp = a[i];
                //2.这个循环运行1次或零次，后面小于则赋值为前面那个
                for (j = i; j >= gap &&
                        tmp.compareTo(a[j - gap]) < 0; j -= gap) {
                    a[j] = a[j - gap];
                }
                //3.若上面有交换，j此时指向前面那个，赋值原来的值
                a[j] = tmp;
            }
        }
    }

分析

希尔排序的最坏情形运行时间为O(n2)