插入排序的优化之希尔排序

希尔排序是插入排序的一种，又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，可以说它是插入排序的高级版。我们可以先回顾一下直接插入排序的过程：

排序前将第一个元素看成有序的数列

• 第 1 趟排序后：得到一个长度为 2 的有序数列
• 第 2 趟排序后：得到一个长度为 3 的有序数列
• 第 3 趟排序后：得到一个长度为 4 的有序数列
• …….. 每趟插入排序，都可以将一个无序值插入一个有序数列，直到全部元素有序

最坏情况下，直接插入排序的时间复杂度是 O (n²)。从上图可以看出，6 这个元素被移动了三次才到末尾。我在直接插入排序的博客 《O (n²) 的三个排序算法》 中写到，直接插入排序最好的情况就是本来就有序，所以直接插入排序用来排序那些近乎有序的数组是非常适合的。 所以我们对于一个无序数组，先把它变成大致有序，然后超级大致有序，然后变成超级超级大致有序…… 最后变成完全有序，这样可以省略掉很多不必要的元素交换 。

那么如何让大元素一开始就分批向后移动呢？那就是通过分组排序的方式， 应该怎么分呢？比如有 10 个元素的序列，分成几个才合适？每次缩减又是多少呢？ 将一个序列分成好几个序列，用一个数来表示：那个数称为增量，我们可以发现增量越来越小，其实就是数组越来越有序的过程。

下面来看看希尔排序的过程：

下面通过代码来实现一下希尔排序：

public static void shellSort(int[] arr){
    // 每次都缩小增量 
    for (int step = arr.length/ 2; step > 0; step /= 2) {
        for (int i = step; i < arr.length; i++) {
            int j = i;
            int tmp = arr [j];
            // 注意这里不是结构上的前一个元素，而是对于组而言的，同组之间的元素交换 
            while(j - step >= 0 && arr [j - step] > tmp){
                arr [j] = arr [j - step];
                j = j - step;
            }
            arr [j] = tmp;
        }
    }
}

希尔排序和直接插入排序的对比，对 30 万个随机数进行排序

最后再思考一个问题，希尔排序是稳定排序吗？

当然不是，因为通过上面的结论我们知道，希尔排序是依靠分组来进行排序的，值相同的元素完全有可能被调换位置，所以希尔排序是一个不稳定排序。