希尔排序（Shell Sort）
希尔排序是插入排序的改进版，通过分组插入排序的方式逐步缩小分组间隔，最终完成整个数组的排序。它的核心思想是让数组中任意间隔为h的元素有序，随着h的减小，数组逐渐趋于全局有序。
算法原理
-
分组插入排序：
- 选择一个增量序列（例如
h = n/2, n/4, ..., 1），将数组分成若干子数组，每个子数组包含间隔为h的元素。 - 对每个子数组进行插入排序。
- 选择一个增量序列（例如
-
逐步缩小增量：
- 每次缩小增量h，重复分组和插入排序的过程，直到h=1。
- 当h=1时，整个数组被当作一个子数组进行插入排序，此时数组已经基本有序，插入排序的效率很高。
算法步骤
- 选择一个增量序列（例如
h = n/2, n/4, ..., 1）。 - 对于每个增量h：
- 将数组分成若干子数组，每个子数组包含间隔为h的元素。
- 对每个子数组进行插入排序。
- 重复上述步骤，直到h=1，完成最后一次插入排序。
示例
假设数组为 [8, 3, 5, 1, 4, 7, 6, 2]，增量序列为 [4, 2, 1]。
第1轮（h=4）：
- 将数组分成4个子数组：
- 子数组1：
[8, 4] - 子数组2：
[3, 7] - 子数组3：
[5, 6] - 子数组4：
[1, 2]
- 子数组1：
- 对每个子数组进行插入排序：
- 子数组1：
[4, 8] - 子数组2：
[3, 7] - 子数组3：
[5, 6] - 子数组4：
[1, 2]
- 子数组1：
- 排序后的数组：
[4, 3, 5, 1, 8, 7, 6, 2]
第2轮（h=2）：
- 将数组分成2个子数组：
- 子数组1：
[4, 5, 8, 6] - 子数组2：
[3, 1, 7, 2]
- 子数组1：
- 对每个子数组进行插入排序：
- 子数组1：
[4, 5, 6, 8] - 子数组2：
[1, 2, 3, 7]
- 子数组1：
- 排序后的数组：
[4, 1, 5, 2, 6, 3, 8, 7]
第3轮（h=1）：
- 将整个数组当作一个子数组进行插入排序：
- 排序后的数组：
[1, 2, 3, 4, 5, 6, 7, 8]
- 排序后的数组：
代码实现
def shell_sort(arr):n = len(arr)# 初始增量hh = n // 2while h > 0:# 对每个子数组进行插入排序for i in range(h, n):temp = arr[i]j = i# 插入排序的核心逻辑while j >= h and arr[j - h] > temp:arr[j] = arr[j - h]j -= harr[j] = temp# 缩小增量h //= 2return arr# 示例
arr = [8, 3, 5, 1, 4, 7, 6, 2]
print(shell_sort(arr)) # 输出: [1, 2, 3, 4, 5, 6, 7, 8]
时间复杂度
-
最好情况：O(n log n)（当数组已经有序时）
-
最坏情况：O(n²)（取决于增量序列的选择）
-
平均情况：O(n log n) ~ O(n²)
空间复杂度
- O(1)（原地排序）
稳定性
- 不稳定（相同元素可能被分到不同的子数组，导致相对顺序改变）
优缺点
优点：
-
比插入排序更快，尤其是对中等规模的数据。
-
实现简单，代码量少。
缺点：
-
时间复杂度依赖于增量序列的选择。
-
不稳定。
适用场景
-
中等规模的数据排序。
-
对稳定性要求不高的场景。
总结
- 希尔排序通过分组插入排序的方式，逐步缩小增量，最终完成排序。
它的时间复杂度介于O(n log n)和O(n²)之间，适合中等规模的数据排序。
虽然不稳定，但在实际应用中表现良好。
© 著作权归作者所有
