主页 > 人工智能 >

算法04-希尔排序

人工智能
2025-09-09 21:42:02

希尔排序（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：[4, 8]子数组2：[3, 7]子数组3：[5, 6]子数组4：[1, 2] 排序后的数组：[4, 3, 5, 1, 8, 7, 6, 2] 第2轮（h=2）：将数组分成2个子数组：子数组1：[4, 5, 8, 6]子数组2：[3, 1, 7, 2] 对每个子数组进行插入排序：子数组1：[4, 5, 6, 8]子数组2：[1, 2, 3, 7] 排序后的数组：[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) # 初始增量h h = n // 2 while 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 -= h arr[j] = temp # 缩小增量 h //= 2 return 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)（原地排序）稳定性不稳定（相同元素可能被分到不同的子数组，导致相对顺序改变）

优缺点优点：

比插入排序更快，尤其是对中等规模的数据。

实现简单，代码量少。

缺点：

时间复杂度依赖于增量序列的选择。

不稳定。

适用场景

中等规模的数据排序。