排序算法丨希尔排序

前言

希尔排序(Shell's Sort),是插入排序的一种,也是直接插入排序算法的一种更高效的改进版本。

1959年7月,美国辛辛那提大学的数学系博士 Donald Shell 在 《ACM 通讯》上发表了希尔排序算法,成为首批将时间复杂度降到 O(n2) 以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是 O(n2),但经过优化的希尔排序可以达到 O(n1.3) 甚至 O(n7/6)。该方法以其设计者希尔(Donald Shell)的名字命名,所以就叫希尔排序。

希尔排序是非稳定的排序算法。

排序思路

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

它的基本思想:

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

增量序列

其中,每一遍排序的间隔在希尔排序中被称之为增量,所有的增量组成的序列称之为增量序列
增量依次递减,最后一个增量必须为 1,所以希尔排序又被称之为“缩小增量排序(Diminishing Increment Sort)”。

要是以专业术语来描述希尔排序,可以分为两个步骤:

  • 定义增量序列 Dm > Dm-1 > Dm-2 > ... > D1 = 1
  • 对每个 Dk 进行 “Dk 间隔排序“

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

  • "Dk+1 间隔” 有序的序列,在经过 “Dk 间隔” 排序后,仍然是 “Dk+1 间隔” 有序的。

增量序列的选择会极大地影响希尔排序的效率。

一般使用的逐步减半的增量序列为 Dm = N/2,Dk = Dk+1/2,这个序列是当年希尔发表此算法的论文中选用的序列,所以也被称之为希尔增量序列

代码实现

public static void shellSort1(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 循环;并且插入时不再是相邻数字挪动,而是以增量为步长挪动。

选择合适的增量序列

增量序列如果选得不好,希尔排序的效率可能比插入排序效率还要低,最坏的时间复杂度依然是 O(n2)。

如下图所示:
选择合适的增量序列

在这个例子中,可以发现,原数组 4 间隔、2 间隔都已经有序了,使用希尔排序时,真正起作用的只有最后一轮 1 间隔排序,也就是直接插入排序。对于这种数组,希尔排序并没有减少直接插入排序的工作量,反而增加了分组操作的成本。

于是人们发现:增量元素不互质,则小增量可能根本不起作用

为了保证每一轮的增量需要彼此互质(除了 1 以外没有其他公约数),人们相继提出多种增量方式,其中比较著名的有 Hibbard 增量序列、Knuth 增量序列、Sedgewick 增量序列。

动画演示

演示动画来自于Data Structure Visualizations


希尔排序

复杂度分析

事实上,希尔排序时间复杂度非常难以分析,它的平均复杂度界于最好的 O(n) 和最坏的 O(n2) 之间,普遍认为它为 O(n1.3)。
希尔排序的空间复杂度为 O(1),只需要常数级的临时变量。

比较

  • 直接插入排序是稳定的,而希尔排序是不稳定的。
  • 直接插入排序可适用于链式存储结构,而希尔排序不适用。
  • 当数据规模越大时,希尔排序相较于直接插入排序的效果更明显。

参考

LeetCode
程序员小灰
趣谈编程
打赏
评论区
头像
文章目录