希尔排序

(图片来自 希尔排序 - 维基百科

思路

希尔排序其实是对插入排序的改进,所以我们先来介绍插入排序的优缺点:

  • (+) 插入排序在排序几乎已经排好序的数据时,效率非常高,甚至可以达到线性的时间复杂度 $O(n)$。
  • (-) 但是在其他一般条件下,由于插入排序每次只能移动一位,效率不高。

为了保持插入排序的优点,克服每次只能移动一位的缺点,希尔排序被提出,其核心思想为「排序时允许每次移动多位」,具体做法是通过构造多个距离(即 步长)较远的多个元素组成的待排序子序列,对其进行插入排序(因此步长较长),然后慢慢减小步长(即慢慢减小插入排序所移动的距离),直到步长为 1。注意,这里不是真的物理上将其分为多个子序列,而是为了方便理解,实际操作就是只需要跟相邻距离为步长的元素相比。其算法步骤如下:

假设待排序数组为 $[k_1, k_2, \cdots, k_n]$,其中 $n$ 为数组长度。

  1. 以数组总长度的一半 $s = \frac{n}{2}$(称为 步长)进行排序,具体做法就是执行 $s$ 次子序列的插入排序,子序列分别为 $[k_1, k_{1 + n}]$、$[k_2, k_{2 + n}]$、……、$[k_s, k_{n}]$。在这样的排序过程中,数组元素会以大步长(即 $s$)移动。
  2. 令 $s = \frac{s}{2}$,重复第一步,直到 $s = 1$。

这里构建这个步长序列可以有很多种方式。上面展示的是以序列长度为初始,每次除以 2,这种方式可能会导致排序效率下降、算法不稳定。举个例子,假如我们先经过步长 5 排序再经过步长 3 排序,那么索引是 15 的倍数的数很有可能会被前后移动,做无用功,并且无法保证算法稳定(可能两个同样数字的后者会被提前交换到前面)。所以可以考虑使用等比的步长序列,例如将第一个步长设置为 2 的若干次方在小于数组长度的前提下的最大值,从而使得排序稳定,且不用做无用功。

根据 维基百科,推荐了以下两个步长序列:

  • 1, 5, 19, 41, 109, ...
  • 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, ...

没太懂这样取的原理。

分析

  • 希尔排序的时间复杂度与选择的步长序列有关,见 维基百科
  • 空间复杂度为 $O(1)$,不需要额外空间。
  • 一般来说,希尔排序是不稳定的算法,除非步长序列是等比数列且每次子序列的排序都使用稳定的排序算法。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。