希尔排序：修订间差异

2025年5月12日 (一) 00:27的最新版本

希尔排序（Shell Sort）是插入排序的一种高效改进版本，由Donald Shell于1959年提出。它通过将原始列表分割成多个子序列进行插入排序，逐步减少子序列的长度，最终完成整体排序。希尔排序的核心思想是通过增量序列（gap sequence）使数据项大跨度移动，减少后续排序的交换次数。

算法原理[编辑 | 编辑源代码]

希尔排序基于以下两个观察： 1. 插入排序对近乎有序的数组效率很高（接近 $O (n)$ 时间复杂度）。 2. 插入排序每次只能将数据项移动一位，效率较低。

希尔排序通过分组插入排序解决这些问题：

选择一个增量序列（如 $g a p = n / 2, n / 4, . . ., 1$ ）。
对每个增量值，将数组分成若干子序列（子序列由相隔gap的元素组成）。
对每个子序列进行插入排序。
逐步缩小增量直至1，此时整个数组已基本有序，最后进行一次标准插入排序。

增量序列[编辑 | 编辑源代码]

常见的增量序列选择方式：

Shell原始序列： $g a p = ⌊ n / 2 ⌋, ⌊ g a p / 2 ⌋, . . ., 1$
Hibbard序列： $2^{k} - 1$ （如1, 3, 7, 15...）
Knuth序列： $(3^{k} - 1) / 2$ （如1, 4, 13, 40...）

算法步骤[编辑 | 编辑源代码]

以Shell原始序列为例的步骤分解： 1. 初始化增量 $g a p = ⌊ n / 2 ⌋$ 2. 对每个子序列（间隔gap的元素组成）进行插入排序 3. 缩小增量： $g a p = ⌊ g a p / 2 ⌋$ 4. 重复步骤2-3直到 $g a p = 1$ 5. 执行最终插入排序

代码实现[编辑 | 编辑源代码]

以下是Python实现示例：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量
    
    while gap > 0:
        # 对各个子序列进行插入排序
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 插入排序过程
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2  # 缩小增量

# 示例
arr = [12, 34, 54, 2, 3]
print("排序前:", arr)
shell_sort(arr)
print("排序后:", arr)

输入/输出示例：

排序前: [12, 34, 54, 2, 3]
排序后: [2, 3, 12, 34, 54]

代码解释： 1. 初始gap设为数组长度的一半（5//2=2） 2. 第一轮处理子序列：[12,54,3]和[34,2] 3. 缩小gap为1后执行标准插入排序

时间复杂度分析[编辑 | 编辑源代码]

希尔排序的时间复杂度取决于增量序列的选择：

时间复杂度对比
增量序列	最坏时间复杂度	平均时间复杂度
Shell原始序列	$O (n^{2})$	$O (n^{1.5})$
Hibbard序列	$O (n^{1.5})$	$O (n^{1.25})$
Knuth序列	$O (n^{1.5})$	$O (n^{1.16})$

空间复杂度： $O (1)$ （原地排序）
稳定性：不稳定排序（相同元素可能因分组而改变相对位置）

实际应用场景[编辑 | 编辑源代码]

希尔排序在以下场景中表现优异： 1. 中等规模数据排序（千级元素）：比 $O (n \log n)$ 算法常数因子更小 2. 内存受限环境：空间复杂度为 $O (1)$ 3. 嵌入式系统：实现简单且不需要递归

典型案例：

Linux内核的`sort()`函数在特定情况下会使用希尔排序变体
早期Java版本的`Arrays.sort()`对小数组使用希尔排序

与其他排序算法对比[编辑 | 编辑源代码]

排序算法对比
算法	平均时间复杂度	空间复杂度	稳定性	适用场景
希尔排序	$O (n^{1.25})$	$O (1)$	不稳定	中等规模数据
插入排序	$O (n^{2})$	$O (1)$	稳定	小规模或基本有序数据
快速排序	$O (n \log n)$	$O (\log n)$	不稳定	大规模随机数据

优化技巧[编辑 | 编辑源代码]

1. 增量序列选择：使用Hibbard或Knuth序列可提升性能 2. 混合排序：当gap较小时切换为插入排序 3. 并行化：不同子序列的排序可并行处理

练习题目[编辑 | 编辑源代码]

1. 实现使用Hibbard序列的希尔排序 2. 分析数组[9,8,7,6,5,4,3,2,1]的希尔排序过程 3. 比较希尔排序与归并排序在10,000个随机整数上的性能差异

总结[编辑 | 编辑源代码]

希尔排序通过分组插入排序的机制，在保持简单实现的同时显著提升了插入排序的效率。虽然其时间复杂度理论上不如快速排序等 $O (n \log n)$ 算法，但在实际应用中因其低开销和良好的缓存局部性，仍然是许多系统的基础排序算法之一。理解希尔排序有助于掌握分治思想和增量优化等重要算法设计技巧。

@@ 第1行： / 第1行： @@
-{{Note|本条目介绍的是希尔排序（Shell Sort），一种基于插入排序的高效排序算法，适用于初学者和需要回顾该算法的程序员。}}
+{{DISPLAYTITLE:希尔排序}}
-== 概述 ==
+'''希尔排序'''（Shell Sort）是[[插入排序]]的一种高效改进版本，由Donald Shell于1959年提出。它通过将原始列表分割成多个子序列进行插入排序，逐步减少子序列的长度，最终完成整体排序。希尔排序的核心思想是'''通过增量序列（gap sequence）使数据项大跨度移动，减少后续排序的交换次数'''。
-'''希尔排序'''（Shell Sort）是[[插入排序]]的一种高效改进版本，由Donald Shell于1959年提出。它通过将原始列表分割成多个子序列进行插入排序，逐步缩小子序列的间隔，最终完成整体排序。希尔排序的时间复杂度优于普通的插入排序（<math>O(n^2)</math>），具体取决于间隔序列的选择。
-=== 核心思想 ===
+== 算法原理 ==
-希尔排序的核心思想是：
+希尔排序基于以下两个观察：
-# 将待排序数组按一定间隔（称为“增量”或“gap”）分成若干子序列。
+. 插入排序对'''近乎有序的数组'''效率很高（接近<math>O(n)</math>时间复杂度）。
+. 插入排序每次只能将数据项移动一位，效率较低。
+希尔排序通过'''分组插入排序'''解决这些问题：
+# 选择一个增量序列（如<math>gap = n/2, n/4, ..., 1</math>）。
+# 对每个增量值，将数组分成若干子序列（子序列由相隔gap的元素组成）。
 # 对每个子序列进行插入排序。
-# 逐步缩小间隔，重复上述过程，直到间隔为1，此时整个数组基本有序，最后进行一次完整的插入排序。
+# 逐步缩小增量直至1，此时整个数组已基本有序，最后进行一次标准插入排序。
+=== 增量序列 ===
+常见的增量序列选择方式：
+* Shell原始序列：<math>gap = \lfloor n/2 \rfloor, \lfloor gap/2 \rfloor, ..., 1</math>
+* Hibbard序列：<math>2^k - 1</math>（如1, 3, 7, 15...）
+* Knuth序列：<math>(3^k - 1)/2</math>（如1, 4, 13, 40...）
 == 算法步骤 ==
-希尔排序的步骤如下：
+以Shell原始序列为例的步骤分解：
-# 选择一个增量序列 <math>gap_1, gap_2, \ldots, gap_k</math>，其中 <math>gap_1 > gap_2 > \ldots > gap_k = 1</math>。
+. 初始化增量<math>gap = \lfloor n/2 \rfloor</math>
-# 对于每个增量 <math>gap_i</math>，将数组分成 <math>gap_i</math> 个子序列，每个子序列包含相隔 <math>gap_i</math> 的元素。
+. 对每个子序列（间隔gap的元素组成）进行插入排序
-# 对每个子序列进行插入排序。
+. 缩小增量：<math>gap = \lfloor gap/2 \rfloor</math>
-# 重复步骤2-3，直到增量为1，完成最后一次插入排序。
+. 重复步骤2-3直到<math>gap = 1</math>
+. 执行最终插入排序
-=== 增量序列 ===
+<mermaid>
-常见的增量序列选择方式包括：
+flowchart TD
-* Shell原始序列：<math>gap = \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \ldots, 1</math>。
+    A[开始] --> B[初始化gap = n/2]
-* Hibbard序列：<math>gap = 2^k - 1</math>（如1, 3, 7, 15, ...）。
+    B --> C{gap >= 1?}
-* Knuth序列：<math>gap = (3^k - 1)/2</math>（如1, 4, 13, 40, ...）。
+    C -->|是| D[对每个gap分组进行插入排序]
+    D --> E[gap = gap/2]
+    E --> C
+    C -->|否| F[最终插入排序]
+    F --> G[结束]
+</mermaid>
 == 代码实现 ==
-以下是希尔排序的Python实现示例，使用Shell原始增量序列：
+以下是Python实现示例：
 <syntaxhighlight lang="python">
@@ 第30行： / 第46行： @@
      n = len(arr)
      gap = n // 2  # 初始增量
      while gap > 0:
+        # 对各个子序列进行插入排序
          for i in range(gap, n):
              temp = arr[i]
              j = i
-             # 对子序列进行插入排序
+             # 插入排序过程
              while j >= gap and arr[j - gap] > temp:
                  arr[j] = arr[j - gap]
                  j -= gap
              arr[j] = temp
-         gap //= 2  # 缩小增量
+         gap = gap // 2  # 缩小增量
-# 示例输入与输出
+# 示例
 arr = [12, 34, 54, 2, 3]
+print("排序前:", arr)
 shell_sort(arr)
-print("排序后的数组:", arr)
+print("排序后:", arr)
 </syntaxhighlight>
-{{Output|
+'''输入/输出示例'''：
-排序后的数组: [2, 3, 12, 34, 54]
+<pre>
-}}
+排序前: [12, 34, 54, 2, 3]
+排序后: [2, 3, 12, 34, 54]
+</pre>
-=== 代码解释 ===
+代码解释：
-. 初始增量 <code>gap</code> 设为数组长度的一半。
+. 初始gap设为数组长度的一半（5//2=2）
-. 对每个增量 <code>gap</code>，从 <code>gap</code> 开始遍历数组，对子序列进行插入排序。
+. 第一轮处理子序列：[12,54,3]和[34,2]
-. 每次循环后，增量缩小为原来的一半，直到增量为1，完成最后一次排序。
+. 缩小gap为1后执行标准插入排序
 == 时间复杂度分析 ==
 希尔排序的时间复杂度取决于增量序列的选择：
-* 最坏情况下（如使用Shell原始序列）：<math>O(n^2)</math>。
-* 最优情况下（如使用Hibbard或Knuth序列）：<math>O(n^{3/2})</math> 或 <math>O(n \log^2 n)</math>。
-== 实际应用案例 ==
+{| class="wikitable"
+|+ 时间复杂度对比
+! 增量序列 !! 最坏时间复杂度 !! 平均时间复杂度
+|-
+| Shell原始序列 || <math>O(n^2)</math> || <math>O(n^{1.5})</math>
+|-
+| Hibbard序列 || <math>O(n^{1.5})</math> || <math>O(n^{1.25})</math>
+|-
+| Knuth序列 || <math>O(n^{1.5})</math> || <math>O(n^{1.16})</math>
+|}
+* 空间复杂度：<math>O(1)</math>（原地排序）
+* 稳定性：'''不稳定'''排序（相同元素可能因分组而改变相对位置）
+== 实际应用场景 ==
 希尔排序在以下场景中表现优异：
-. '''中等规模数据排序'''：当数据量不大（如几千到几万）时，希尔排序比 <math>O(n \log n)</math> 的算法（如快速排序）更高效，因为其常数因子较小。
+. '''中等规模数据排序'''（千级元素）：比<math>O(n \log n)</math>算法常数因子更小
-. '''嵌入式系统'''：由于希尔排序是原地排序（不需要额外空间），适合内存受限的环境。
+. '''内存受限环境'''：空间复杂度为<math>O(1)</math>
-. '''部分有序数据'''：若数据已基本有序，希尔排序的插入排序步骤会非常高效。
+. '''嵌入式系统'''：实现简单且不需要递归
-== 示例图表 ==
+'''典型案例'''：
-以下是一个希尔排序过程的示意图（使用Shell原始序列，初始gap=2）：
+* Linux内核的`sort()`函数在特定情况下会使用希尔排序变体
+* 早期Java版本的`Arrays.sort()`对小数组使用希尔排序
-<mermaid>
+== 与其他排序算法对比 ==
-graph TD
+{| class="wikitable"
-    A[原始数组: 12, 34, 54, 2, 3] --> B[gap=2: 子序列1=12,54,3; 子序列2=34,2]
+|+ 排序算法对比
-    B --> C[子序列1排序后: 3,12,54]
+! 算法 !! 平均时间复杂度 !! 空间复杂度 !! 稳定性 !! 适用场景
-    B --> D[子序列2排序后: 2,34]
+|-
-    C --> E[合并后数组: 3, 2, 12, 34, 54]
+| '''希尔排序''' || <math>O(n^{1.25})</math> || <math>O(1)</math> || 不稳定 || 中等规模数据
-    D --> E
+|-
-    E --> F[gap=1: 最终插入排序]
+| 插入排序 || <math>O(n^2)</math> || <math>O(1)</math> || 稳定 || 小规模或基本有序数据
-    F --> G[排序完成: 2, 3, 12, 34, 54]
+|-
-</mermaid>
+| 快速排序 || <math>O(n \log n)</math> || <math>O(\log n)</math> || 不稳定 || 大规模随机数据
+|}
+== 优化技巧 ==
+. '''增量序列选择'''：使用Hibbard或Knuth序列可提升性能
+. '''混合排序'''：当gap较小时切换为插入排序
+. '''并行化'''：不同子序列的排序可并行处理
-== 与其他排序算法的比较 ==
+== 练习题目 ==
-* '''插入排序'''：希尔排序是插入排序的改进版，通过分组减少了元素移动次数。
+. 实现使用Hibbard序列的希尔排序
-* '''快速排序'''：希尔排序在中等规模数据中可能更快，但快速排序的平均时间复杂度更低（<math>O(n \log n)</math>）。
+. 分析数组[9,8,7,6,5,4,3,2,1]的希尔排序过程
-* '''归并排序'''：归并排序需要额外空间，而希尔排序是原地排序。
+. 比较希尔排序与归并排序在10,000个随机整数上的性能差异
 == 总结 ==
-希尔排序是一种简单但高效的排序算法，特别适合中等规模数据或内存受限的场景。尽管其时间复杂度不如快速排序或归并排序，但在实际应用中仍有一席之地。理解希尔排序有助于掌握分组排序的思想，并为学习更复杂的算法打下基础。
+希尔排序通过'''分组插入排序'''的机制，在保持简单实现的同时显著提升了插入排序的效率。虽然其时间复杂度理论上不如快速排序等<math>O(n \log n)</math>算法，但在实际应用中因其低开销和良好的缓存局部性，仍然是许多系统的基础排序算法之一。理解希尔排序有助于掌握'''分治思想'''和'''增量优化'''等重要算法设计技巧。
-{{Stub|algorithm}}
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
 [[Category:排序算法]]