希尔排序

raw/articles/2026/05/希尔排序.md

一句话总结

希尔排序是基于插入排序的简单改进，通过预处理增加数组的局部有序性，突破了插入排序的 $O(N^2)$ 时间复杂度。

核心要点

1. h 有序数组的概念

一个数组是 h 有序的，是指这个数组中任意间隔为 h（或者说间隔元素的个数为 h-1）的元素都是有序的。这是希尔排序的核心理论基础。

2. 基于插入排序的改进

希尔排序通过对数组进行预处理（使其变成 h 有序数组），增加数组的局部有序性，从而让后续的插入排序更加高效。

3. 时间复杂度突破

通过巧妙的间隔序列设计，希尔排序能够突破插入排序的 $O(N^2)$ 时间复杂度限制。

基本原理

希尔排序的核心思想是：

1. 先使数组变成 h 有序数组（对于任意 h）
2. 逐步减小 h 的值
3. 当 h=1 时，数组已经基本有序，此时进行最后一次插入排序

算法可视化：

相关题目

平台	题目	难度
LeetCode	912. 排序数组	中等

相关概念

• 插入排序：希尔排序的基础算法
• 选择排序：前置知识之一
• h 有序数组：
• 时间复杂度：

相关实体

• 《算法4》： 本文作者首次了解希尔排序的出处

总结

希尔排序通过将数组预处理成 h 有序状态，显著提升了插入排序的性能，是一个"简单优化带来巨大提升"的经典案例。

待补充

由于原文无法完整获取（在"Loading comments..."处截断），以下内容缺失：

• h 有序数组的完整示例和图示
• 希尔排序的完整算法步骤
• 间隔序列（gap sequence）的选择策略
• 完整的时间复杂度分析
• 代码实现
• 与其他排序算法的对比

如需完整内容，请手动复制原文后重新摄取。