希尔排序

十大经典排序算法

希尔排序（Shellsort）使用的是增量递减排序法，就是首先使用一个增量 step ，这个增量可以理解为元素之间的间隔，把数组分组，然后单独排序，这样每组都是有序的，然后增量减半，当增量为 1 的时候相当于对整个数组进行排序。这个增量不一定每次非要减半，减三分之一也可以，但无轮怎么减，都要保证最后一次增量一定是 1 ，如下图所示。

我们假设第一轮增量值是 4 ，相当于把相距为 4 的元素分为一组然后排序，接着减少增量，继续比较，当增量为 1 的时候相当于前后两个比较然后交换，在往前面的都是比较小的，没必要在交换了。可以看到如果增量 step 为 1 的时候，代码和插入排序完全一样。

public void shellSort(int[] nums) {
    int length = nums.length;
    for (int step = length >> 1; step >= 1; step >>= 1) {
        for (int i = step; i < length; i++) {
            int key = nums[i];
            int j = i - step;
            // 大于key的往后挪。
            for (; j >= 0 && nums[j] > key; j -= step)
                nums[j + step] = nums[j];
            nums[j + step] = key;// 把key放到合适的位置。
        }
    }
}

稳定性分析

希尔排序使用的是增量递减排序法，可以理解为分组，相同的元素可以分到不同组，所以如果有相同的元素，后面的有可能会挪到前面，所以他是不稳定的。上面嵌套有 3 个 for 循环，其中第一个每次减半，时间复杂度是 O(log(n)) ，第二个时间复杂度是 O(n) ，第三个最开始的时候间隔比较大，执行次数比较少，到最后间隔比较小的时候，很多区域都是有序的了，比如当间隔为 1 的时候，相当于前后比较两两交换，最多执行 1 次，总体来说时间复杂度可以认为是 O(log(n)) ，所以整个希尔排序的时间复杂度是 O(log(n)*n*log(n)) 。

时间复杂度： O(n*log(n)^2)
稳定性：不稳定

相关链接