算法04-希尔排序

希尔排序（Shell Sort）

希尔排序是插入排序的改进版，通过分组插入排序的方式逐步缩小分组间隔，最终完成整个数组的排序。它的核心思想是让数组中任意间隔为h的元素有序，随着h的减小，数组逐渐趋于全局有序。

算法原理

1. 分组插入排序：

   • 选择一个增量序列（例如 h = n/2, n/4, ..., 1），将数组分成若干子数组，每个子数组包含间隔为h的元素。
   • 对每个子数组进行插入排序。

2. 逐步缩小增量：

   • 每次缩小增量h，重复分组和插入排序的过程，直到h=1。
   • 当h=1时，整个数组被当作一个子数组进行插入排序，此时数组已经基本有序，插入排序的效率很高。

算法步骤

1. 选择一个增量序列（例如 h = n/2, n/4, ..., 1）。
2. 对于每个增量h：
   • 将数组分成若干子数组，每个子数组包含间隔为h的元素。
   • 对每个子数组进行插入排序。
3. 重复上述步骤，直到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)（原地排序）

稳定性

• 不稳定（相同元素可能被分到不同的子数组，导致相对顺序改变）

优缺点

优点：

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

• 实现简单，代码量少。

缺点：

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

• 不稳定。

适用场景

• 中等规模的数据排序。

• 对稳定性要求不高的场景。

总结

• 希尔排序通过分组插入排序的方式，逐步缩小增量，最终完成排序。
  它的时间复杂度介于O(n log n)和O(n²)之间，适合中等规模的数据排序。
  虽然不稳定，但在实际应用中表现良好。

© 著作权归作者所有