希尔排序

算法思想

希尔排序法又称缩小增量法，是在直接插入排序基础上的一个优化版。

对于直接插入排序在面对一些特殊情况时，效率非常低（例如：将降序排成升序），而对于已经接近排好的序列，效率非常高。

希尔排序在直接排序之前，进行预排列，将某些极端数据更快的排列到数列前面，构成一个接近排列好的序列，最后再进行一次直接插入排序。

预排列的原理也是插入排列，只不过这里的将数组分成了gap组，分别对每一个小组进行插入排序。

如下动图：对于升序，当gap从5 – 2 – 1的过程中，排在后面的数值小的数能更快排到前面，当gap为1的时候实际上就是进行了一次插入排序。

实现代码

    public void shellSqrt(int[] arr) {
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                temp = arr[i];
                int j;
                for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }

算法特性

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，一般来说为O(n^1.3)。
4. 稳定性：不稳定。

详细的代码点击跳转