希尔排序

希尔排序是插入排序的一种优化，极端情况下，插入排序的数据交换次数非常多，性能差；希尔排序是取间隔较远的数据进行插入排序，这样数组会变得相对有序，最后再进行一次完整插入排序；这样的好处是，相对有序的数组进行插入排序数据交换次数会大大减少，关键是步长的设定。据研究希尔排序时间复杂度O(n^1.3)。

描述：

1、先设定一个步长，原数组内相隔步长的元素组成一个数组（如示例图），对步长数组进行插入排序；
2、根据数组长度选取多个不同步长重复以上过程；
3、几次插入排序后，数组已经逐渐有序，最后再进行一次步长为1的插入排序，排序完成。

资料：

已知的最好步长序列由Marcin Ciura设计（1，4，10，23，57，132，301，701，1750，…）
这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。” 用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快， 但是在涉及大量数据时希尔排序还是比快速排序慢。

示例图：

希尔排序.png

动画：

希尔排序.gif

代码：

    private void shellSort(int[] array, int step) {
        for (int i = 0; i < step; i++) {
            for (int j = i + step; j < array.length; j += step) {
                int index = j;
                int temp = array[index];
                while (index >= step && temp < array[index - step]) {
                    array[index] = array[index - step];
                    index = index - step;
                }
                if (index != j) {
                    array[index] = temp;
                }
            }
        }
    }