编辑“︁希尔排序”︁

{{Note|本条目介绍的是希尔排序（Shell Sort），一种基于插入排序的高效排序算法，适用于初学者和需要回顾该算法的程序员。}}

== 概述 ==
'''希尔排序'''（Shell Sort）是[[插入排序]]的一种高效改进版本，由Donald Shell于1959年提出。它通过将原始列表分割成多个子序列进行插入排序，逐步缩小子序列的间隔，最终完成整体排序。希尔排序的时间复杂度优于普通的插入排序（<math>O(n^2)</math>），具体取决于间隔序列的选择。

=== 核心思想 ===
希尔排序的核心思想是：
# 将待排序数组按一定间隔（称为“增量”或“gap”）分成若干子序列。
# 对每个子序列进行插入排序。
# 逐步缩小间隔，重复上述过程，直到间隔为1，此时整个数组基本有序，最后进行一次完整的插入排序。

== 算法步骤 ==
希尔排序的步骤如下：
# 选择一个增量序列 <math>gap_1, gap_2, \ldots, gap_k</math>，其中 <math>gap_1 > gap_2 > \ldots > gap_k = 1</math>。
# 对于每个增量 <math>gap_i</math>，将数组分成 <math>gap_i</math> 个子序列，每个子序列包含相隔 <math>gap_i</math> 的元素。
# 对每个子序列进行插入排序。
# 重复步骤2-3，直到增量为1，完成最后一次插入排序。

=== 增量序列 ===
常见的增量序列选择方式包括：
* Shell原始序列：<math>gap = \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \ldots, 1</math>。
* Hibbard序列：<math>gap = 2^k - 1</math>（如1, 3, 7, 15, ...）。
* Knuth序列：<math>gap = (3^k - 1)/2</math>（如1, 4, 13, 40, ...）。

== 代码实现 ==
以下是希尔排序的Python实现示例，使用Shell原始增量序列：

<syntaxhighlight lang="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 //= 2  # 缩小增量

# 示例输入与输出
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("排序后的数组:", arr)
</syntaxhighlight>

{{Output|
排序后的数组: [2, 3, 12, 34, 54]
}}

=== 代码解释 ===
1. 初始增量 <code>gap</code> 设为数组长度的一半。
2. 对每个增量 <code>gap</code>，从 <code>gap</code> 开始遍历数组，对子序列进行插入排序。
3. 每次循环后，增量缩小为原来的一半，直到增量为1，完成最后一次排序。

== 时间复杂度分析 ==
希尔排序的时间复杂度取决于增量序列的选择：
* 最坏情况下（如使用Shell原始序列）：<math>O(n^2)</math>。
* 最优情况下（如使用Hibbard或Knuth序列）：<math>O(n^{3/2})</math> 或 <math>O(n \log^2 n)</math>。

== 实际应用案例 ==
希尔排序在以下场景中表现优异：
1. '''中等规模数据排序'''：当数据量不大（如几千到几万）时，希尔排序比 <math>O(n \log n)</math> 的算法（如快速排序）更高效，因为其常数因子较小。
2. '''嵌入式系统'''：由于希尔排序是原地排序（不需要额外空间），适合内存受限的环境。
3. '''部分有序数据'''：若数据已基本有序，希尔排序的插入排序步骤会非常高效。

== 示例图表 ==
以下是一个希尔排序过程的示意图（使用Shell原始序列，初始gap=2）：

<mermaid>
graph TD
    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]
    D --> E
    E --> F[gap=1: 最终插入排序]
    F --> G[排序完成: 2, 3, 12, 34, 54]
</mermaid>

== 与其他排序算法的比较 ==
* '''插入排序'''：希尔排序是插入排序的改进版，通过分组减少了元素移动次数。
* '''快速排序'''：希尔排序在中等规模数据中可能更快，但快速排序的平均时间复杂度更低（<math>O(n \log n)</math>）。
* '''归并排序'''：归并排序需要额外空间，而希尔排序是原地排序。

== 总结 ==
希尔排序是一种简单但高效的排序算法，特别适合中等规模数据或内存受限的场景。尽管其时间复杂度不如快速排序或归并排序，但在实际应用中仍有一席之地。理解希尔排序有助于掌握分组排序的思想，并为学习更复杂的算法打下基础。

{{Stub|algorithm}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:排序算法]]