希尔排序

在这篇文章里专门讲过插入排序算法https://www.jianshu.com/p/5d071ca9a039，我们再回顾一下其排序过程：

插入排序.png

可以看到图中，第4轮插入时数组为 [3, 4, 5, 6, 0]，需要将 0 插入到前面的有序数组中，你会发现0是最小的数据，最后要经过 4 轮比较才能将其插入到数组的第一个位置。我们可以得出一个规律：假设某种极端情况下，每轮插入时，待插入的数据与前面排好序的数据相比都是最小的，那么每轮都要比较完所有的数据，但反之，待插入数据与其前面有序数据相比都是最大的，则只需要比较一次。这都是极端情况，但是如果数组后面的数据都比较小，则要比较的次数肯定多，要经过很多次数据挪移操作，那么我们有没什么方法，尽可能快地将数组后面的小数据搬移到数组前面呢？这样就能减少数据比较搬移操作，以提升效率。

答案是肯定的，它就是希尔排序，希尔排序是直接插入排序的一种优化方案。假设数组有 n 条数据，并且第 n 条数据是数组里最小的。要将第 n 条数据交换到最前面，必然要比较 n -1 次，但是如果我们最先开始隔 n/2 个数据进行比较呢，那么第 n 个数据要搬移到最前面，只需要 1 或者 2 次比较就能被搬移到数组比较靠前的位置了。

我们定义这个间隔数叫 gap，每次我们对数组中的 [0+a, gap+a, 2*gap+a, 3 * gap+a...](a < gap, a取值范围[0, gap)) 进行插入排序，保持数组中这些位置的元素是相对有序的。gap 最开始是一个比较大的值，做完一轮之后，再缩小 gap 的值重复执行，当 gap 缩小到 1 时，就退化成前面我们讲的选择排序了，但是这个时候我们已经将数组后面相对较小的数搬移到前面了，最后一轮插入排序时要进行比较以及数据挪移的次数会越来越少了。

看如下算法示意图（注意这并不是实际执行顺序，而是一个最终的效果示意）：

希尔排序.png

在这里会进行多次插入排序，但每次排序的数据量是不一样的，gap 越大数据量越小，比较小的数据能尽快交换到数组前面。随着 gap 的递减，排序的数据量越大，但是这个时候需要比较的次数也会越来越少了。

最后上代码如下：

fun shellSort(array: IntArray?) {
    array ?: return
    if (array.isEmpty())
        return
    var gap = array.size / 2
    while (gap > 0) {
        for (i in gap until array.size) {
            var target = array[i]
            var j = i - gap
            while (j >= 0 && array[j] > target) {
                array[j + gap] = array[j]
                j -= gap
            }
            array[j + gap] = target
        }
        gap /= 2
    }
}

空间复杂度：O(1)
时间复杂度：O(n²)
希尔排序是不稳定的，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

最后，关于 gap 值的选择，这里很粗暴的选择了 n/2 这样每次递减，但实际上这样并不是高效的，关于这个话题不在这里做讨论，网上有更详细的文章说明，这里只是了解这个算法的核心思想。