文章目录
- 一、原理
- 二、步骤
- 三、时间复杂度
- 四、空间复杂度
- 五、可视化过程
- 六、示例代码
- 七、适用场景
- 八、不适用场景
- 九、相关文章
一、原理
希尔排序是插入排序的改进版本，也称为缩小增量排序。它通过将数组分成多个子序列（按一定间隔 gap 划分），对每个子序列进行插入排序，然后逐步缩小 gap，最终对整个数组进行一次标准的插入排序。
特点：通过分组增量（gap）进行预处理。
以发明者 Donald Shell 的名字命名。
二、步骤
三、时间复杂度
最坏情况：O(n²)（取决于 gap 的选择）。 平均情况：O(n log n) ~ O(n^(3/2))（取决于 gap 序列）。 最好情况：O(n log n)（当数组已经部分有序时）。
四、空间复杂度
O(1)（原地排序）。
五、可视化过程
初始数组：[12, 34, 54, 2, 3, 9, 8, 7, 6, 5]
gap = 5：分组为 [12, 9], [34, 8], [54, 7], [2, 6], [3, 5]，分别插入排序 → [9, 8, 7, 2, 3, 12, 34, 54, 6, 5]
gap = 2：分组为 [9, 7, 3, 34, 6], [8, 2, 12, 54, 5]，分别插入排序 → [3, 2, 6, 5, 9, 8, 7, 12, 34, 54]
gap = 1：对整个数组插入排序 → [2, 3, 5, 6, 7, 8, 9, 12, 34, 54]
六、示例代码
def shell_sort(arr):
n = len(arr)
gap = n // 2 # 初始 gap 取数组长度的一半
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 # 缩小 gap
return arr
# 测试示例
if __name__ == "__main__":
data = [12, 34, 54, 2, 3, 9, 8, 7, 6, 5]
print("排序前:", data)
sorted_data = shell_sort(data.copy())
print("排序后:", sorted_data)
排序前: [12, 34, 54, 2, 3, 9, 8, 7, 6, 5]
排序后: [2, 3, 5, 6, 7, 8, 9, 12, 34, 54]
七、适用场景
- 适用于中等规模的数据集。
- 在数据部分有序或需要原地排序且对稳定性无严格要求时表现良好。
- 常用于嵌入式系统或内存受限场景，因为其空间复杂度为 O(1)。
- 不适合对稳定性要求高的场景，因为希尔排序是不稳定的排序算法。
八、不适用场景
- 对排序稳定性有严格要求的情况
- 小规模或几乎有序的数据集
- 大规模且完全随机的数据
- 需要严格时间复杂度保证的场景
希尔排序为什么不稳定
- 跨距离交换：元素可能跨过多个位置进行交换
- 分组独立排序：相同的元素可能位于不同的分组中，各自独立移动
- 相对位置破坏：排序过程中，相等元素的原始相对顺序可能被破坏
九、相关文章
Python冒泡排序原理与示例 Python选择排序原理与示例 Python插入排序原理与示例 Python堆排序原理与示 Python归并排序原理与示例 Python希尔排序原理与示例（当前） Python快速排序原理与示例
