排序算法：希尔排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了排序算法：希尔排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1959 年 7 月，美国辛辛那提大学的数学系博士 Donald Shell 在《ACM 通讯》上发表了希尔排序算法，成为首批将时间复杂度降到 O(n²)以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是 O(n²) ，但经过优化的希尔排序可以达到 O(n^1.3)甚至O(n^7/6)。

略为遗憾的是，所谓「一将功成万骨枯」，希尔排序和冒泡、选择、插入等排序算法一样，逐渐被快速排序所淘汰，但作为承上启下的算法，不可否认的是，希尔排序身上始终闪耀着算法之美。

希尔排序本质上是对插入排序的一种优化，它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。它的基本思想是：

将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
逐渐缩小间隔进行下一轮排序
最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成

举个例子，对数组 [84,83,88,87,61,50,70,60,80,99] 进行希尔排序的过程如下：

第一遍（5间隔排序）：按照间隔 5 分割子数组，共分成五组，分别是 [84,50],[83,70],[88,60],[87,80],[61,99]。对它们进行插入排序，排序后它们分别变成： [50,84],[70,83],[60,88],[80,87],[61,99]，此时整个数组变成 [50,70,60,80,61,84,83,88,87,99]。
第二遍（2间隔排序）：按照间隔2分割子数组，共分成两组，分别是 [50,60,61,83,87],[70,80,84,88,99]。对他们进行插入排序，排序后它们分别变成：[50,60,61,83,87],[70,80,84,88,99]，此时整个数组变成 [50,70,60,80,61,84,83,88,87,99]。这里有一个非常重要的性质：当我们完成 2 间隔排序后，这个数组仍然是保持 5 间隔有序的。也就是说，更小间隔的排序没有把上一步的结果变坏。
第三遍（1 间隔排序，等于直接插入排序）：按照间隔1分割子数组，分成一组，也就是整个数组。对其进行插入排序，经过前两遍排序，数组已经基本有序了，所以这一步只需经过少量交换即可完成排序。排序后数组变成 [50,60,61,70,80,83,84,87,88,99]，整个排序完成。

其中，每一遍排序的间隔在希尔排序中被称之为增量，所有的增量组成的序列称之为增量序列，也就是本例中的 [5,2,1]。增量依次递减，最后一个增量必须为1，所以希尔排序又被称之为「缩小增量排序」。要是以专业术语来描述希尔排序，可以分为以下两个步骤：

定义增量序列 D m>D m−1>D m−2>...>D 1 =1
对每个 Dk 进行「Dk 间隔排序」

有一条非常重要的性质保证了希尔排序的效率：

「D k+1间隔」有序的序列，在经过「D k间隔」排序后，仍然是「D k+1间隔」有序的

增量序列的选择会极大地影响希尔排序的效率。本例中，我们采用的增量序列为
D m=N/2,D k =D k+1/2，这个序列正是当年希尔发表此算法的论文时选用的序列，所以也被称之为希尔增量序列。代码实现如下：

public static void shellSort(int[] arr) {
    // 间隔序列，在希尔排序中我们称之为增量序列
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 分组
        for (int groupStartIndex = 0; groupStartIndex < gap; groupStartIndex++) {
            // 插入排序
            for (int currentIndex = groupStartIndex + gap; currentIndex < arr.length; currentIndex += gap) {
                // currentNumber 站起来，开始找位置
                int currentNumber = arr[currentIndex];
                int preIndex = currentIndex - gap;
                while (preIndex >= groupStartIndex && currentNumber < arr[preIndex]) {
                    // 向后挪位置
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                // currentNumber 找到了自己的位置，坐下
                arr[preIndex + gap] = currentNumber;
            }
        }
    }
}

这份代码与我们上文中提到的思路是一模一样的，先分组，再对每组进行插入排序。同样地，这里的插入排序也可以采用交换元素的方式。

实际上，这段代码可以优化一下。我们现在的处理方式是：处理完一组间隔序列后，再回来处理下一组间隔序列，这非常符合人类思维。但对于计算机来说，它更喜欢从第 gap 个元素开始，按照顺序将每个元素依次向前插入自己所在的组这种方式。虽然这个过程看起来是在不同的间隔序列中不断跳跃，但站在计算机的角度，它是在访问一段连续数组。

public static void shellSort(int[] arr) {
    // 间隔序列，在希尔排序中我们称之为增量序列
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
        for (int i = gap; i < arr.length; i++) {
            // currentNumber 站起来，开始找位置
            int currentNumber = arr[i];
            // 该组前一个数字的索引
            int preIndex = i - gap;
            while (preIndex >= 0 && currentNumber < arr[preIndex]) {
                // 向后挪位置
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            // currentNumber 找到了自己的位置，坐下
            arr[preIndex + gap] = currentNumber;
        }
    }
}

经过优化之后，这段代码看起来就和插入排序非常相似了，区别仅在于希尔排序最外层嵌套了一个缩小增量的 for 循环；并且插入时不再是相邻数字挪动，而是以增量为步长挪动。文章来源地址https://www.toymoban.com/news/detail-682375.html

到了这里，关于排序算法：希尔排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！