希尔排序

发表于 | 分类于

希尔排序（Shell Sort），也称递减增量排序算法，通过将原始列表拆分为若干较小的子列表（其中每个子列表使用插入排序）进行排序。希尔排序是插入排序的一种更高效的改进版本。

算法描述

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

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

单次示例

以列表 [54, 26, 93, 17, 77, 31, 44, 55, 20] 为例，如果我们使用增量 3，则可以划分为三个子列表：

对每个子列表进行排序之后，我们会得到以下列表：

虽然这个列表并没有完全排序，但是已经很接近最终结果。就本例而言，再移 4 次就可以得到完全的排序列表：

如果我们使用增量 4，则可以划分为三个子列表，也可以进行子列表划分和排序：

完整描述

  1. 选定步长 gap（小于数据的总长度）。
  2. 按步长将数据分组。
  3. 对划分出来的每个组，分别进行插入排序。
  4. 重新选取步长 gap（小于上次的步长）并重复步骤 2~3，直到对最终步长 1 分组排序完毕。

步长序列

步长的选择是希尔排序的重要部分。步长从大到小递减，只要最终步长为 1（算法变为插入排序），任何步长序列都可以工作。

以下是几种不同的增量序列：

增量序列 增量公式
原始 Shell 序列：n/2, n/4, …, 1 $n/2^i$
Hibbard 序列：1, 3, 7, … $2^k - 1$
Knuth 序列：1, 4, 13, … $(2^k - 1)/2$
Sedgewick 序列：1, 5, 19, 41, 109, … $9(4^k – 2^k) + 1$ 与 $2^{k+2} (2^{k+2} – 3) + 1$ 的并集

Python 实现

算法的 Python 代码如下（以原始 Shell 序列为例）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def shell_sort(var):
    gap = len(var) // 2
    while gap > 0:
        for index in range(gap, len(var)):
            val_to_insert = var[index]
            pos = index
            while pos >= gap and var[pos - gap] > val_to_insert:
                var[pos] = var[pos - gap]
                pos = pos - gap
            var[pos] = val_to_insert
        gap = gap // 2


a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(a)
print(a)  # output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

位于 $O(n\log n)$ 和 $O(n^2)$ 之间，跟步长序列有关，以下列出其中两个常用序列的时间复杂度。

原始 Shell 序列：

  • 平均时间复杂度：$O(n^2)$
  • 最坏时间复杂度：$O(n^2)$

Hibbard 序列：

  • 平均时间复杂度：$O(n^{3/2})$
  • 最坏时间复杂度：$O(n^{3/2})$