Python 算法教程（4）：希尔排序详解
前言
希尔排序是插入排序的优化版本，通过分组插入突破 O(n²)。
一、算法原理
分组插入：选择增量序列，按增量分组，对每组插入排序，缩小增量重复。
二、代码实现
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
return arr三、复杂度
最好 O(n log n)，平均 O(n log² n)，最坏 O(n²)
总结
希尔排序通过分组插入减少数据移动。
下一篇：归并排序
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
