Python程序实现希尔排序

希尔排序，又称缩小增量排序，也是一种插入排序算法。希尔排序是将整个数据集分为若干个子集，进行插入排序的变体。

算法描述

首先，设定一个间隔序列 increment，并对数据集按照 increment 的大小进行分组，对每一组数据进行插入排序。随着 increment 逐渐变小，每组包含的元素越来越少，当 increment 为 1 时，整个数据集合并成了一个组，此时插入排序完成。

示例代码：

def shellSort(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^{\frac{3}{2}})

空间复杂度：O(1)

稳定性：不稳定

示例

• 对数组 [64, 34, 25, 12, 22, 11, 90] 进行排序

arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
sorted_arr = shellSort(arr)
print("排序后:", sorted_arr)

输出结果：

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]

结论

希尔排序是一种优化后的插入排序算法，主要通过分组和插入排序实现。希尔排序的时间复杂度为 O(n^{\frac{3}{2}})，空间复杂度为 O(1)，不稳定排序算法。