Python排序算法之希尔排序怎么实现

希尔排序（Shell Sort）是一种基于插入排序的排序算法，由Donald Shell于1959年提出。它通过将待排序的数组分割成若干个子序列，分别进行插入排序，随着子序列逐渐变短，最终整个数组变得基本有序，最后再进行一次插入排序。希尔排序的核心思想是通过逐步减少增量（gap）来使得数组逐渐趋于有序。

希尔排序的基本思想

希尔排序的基本思想是将数组按照一定的增量（gap）分成若干个子序列，对每个子序列进行插入排序。随着增量的逐渐减小，子序列的长度逐渐变短，最终当增量为1时，整个数组就变成了一个子序列，此时进行最后一次插入排序，数组就变得有序了。

希尔排序的实现步骤

1. 选择增量序列：希尔排序的关键在于选择合适的增量序列。常见的增量序列有希尔增量（gap = n/2, gap = gap/2）、Hibbard增量（gap = 2^k - 1）等。本文以希尔增量为例。

2. 分组插入排序：根据当前增量将数组分成若干个子序列，对每个子序列进行插入排序。

3. 缩小增量：逐步缩小增量，重复步骤2，直到增量为1。

4. 最后一次插入排序：当增量为1时，对整个数组进行一次插入排序，排序完成。

Python实现希尔排序

下面是一个使用Python实现希尔排序的示例代码：

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

# 示例
arr = [12, 34, 54, 2, 3]
print("排序前:", arr)
sorted_arr = shell_sort(arr)
print("排序后:", sorted_arr)

代码解析

• gap = n // 2：初始增量为数组长度的一半。
• while gap > 0：当增量大于0时，继续排序。
• for i in range(gap, n)：从增量位置开始，对每个子序列进行插入排序。
• while j >= gap and arr[j - gap] > temp：在子序列中进行插入排序，将较大的元素向后移动。
• gap //= 2：每次循环后，缩小增量。

示例输出

排序前: [12, 34, 54, 2, 3]
排序后: [2, 3, 12, 34, 54]

希尔排序的时间复杂度

希尔排序的时间复杂度取决于增量序列的选择。对于希尔增量序列，最坏情况下的时间复杂度为O(n^2)，但对于某些增量序列（如Hibbard增量），时间复杂度可以降低到O(n^(³⁄₂))。希尔排序的平均时间复杂度通常被认为是O(n log n)。

总结

希尔排序是一种改进的插入排序算法，通过逐步缩小增量来使得数组逐渐趋于有序。虽然它的时间复杂度不如快速排序或归并排序那样优秀，但在某些特定情况下，希尔排序仍然是一个不错的选择。通过选择合适的增量序列，可以进一步提高希尔排序的性能。