编辑“︁希尔排序”︁

{{DISPLAYTITLE:希尔排序}}

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

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

希尔排序通过'''分组插入排序'''解决这些问题：
# 选择一个增量序列（如<math>gap = n/2, n/4, ..., 1</math>）。
# 对每个增量值，将数组分成若干子序列（子序列由相隔gap的元素组成）。
# 对每个子序列进行插入排序。
# 逐步缩小增量直至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原始序列为例的步骤分解：
1. 初始化增量<math>gap = \lfloor n/2 \rfloor</math>
2. 对每个子序列（间隔gap的元素组成）进行插入排序
3. 缩小增量：<math>gap = \lfloor gap/2 \rfloor</math>
4. 重复步骤2-3直到<math>gap = 1</math>
5. 执行最终插入排序

<mermaid>
flowchart TD
    A[开始] --> B[初始化gap = n/2]
    B --> C{gap >= 1?}
    C -->|是| D[对每个gap分组进行插入排序]
    D --> E[gap = gap/2]
    E --> C
    C -->|否| F[最终插入排序]
    F --> G[结束]
</mermaid>

== 代码实现 ==
以下是Python实现示例：

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

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

'''输入/输出示例'''：
<pre>
排序前: [12, 34, 54, 2, 3]
排序后: [2, 3, 12, 34, 54]
</pre>

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

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

{| 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>（原地排序）
* 稳定性：'''不稳定'''排序（相同元素可能因分组而改变相对位置）

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

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

== 与其他排序算法对比 ==
{| class="wikitable"
|+ 排序算法对比
! 算法 !! 平均时间复杂度 !! 空间复杂度 !! 稳定性 !! 适用场景
|-
| '''希尔排序''' || <math>O(n^{1.25})</math> || <math>O(1)</math> || 不稳定 || 中等规模数据
|-
| 插入排序 || <math>O(n^2)</math> || <math>O(1)</math> || 稳定 || 小规模或基本有序数据
|-
| 快速排序 || <math>O(n \log n)</math> || <math>O(\log n)</math> || 不稳定 || 大规模随机数据
|}

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

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

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]