Python实现希尔排序算法

2023-04-16 00:00:00 算法 排序 希尔

希尔排序又称缩小增量排序，是插入排序的一种变体。其基本思想是先将待排序的序列进行分组（通常称为增量），对每组进行插入排序，然后逐步缩小增量，重复上述操作，直到增量为1，最后进行一次完整的插入排序。因为在序列被分组后，每个元素不仅能够和相邻的元素比较，还能够和相距较远的元素比较，因此希尔排序的比较次数会比插入排序少，所以效率也更高。

以下是Python实现希尔排序的代码：

def shell_sort(arr):
    n = len(arr)
    # 初始增量为数组长度的一半
    gap = n // 2
    while gap > 0:
        # 对每组进行插入排序
        for i in range(gap, n):
            j = i
            while j >= gap and arr[j-gap] > arr[j]:
                arr[j-gap], arr[j] = arr[j], arr[j-gap]
                j -= gap
        # 缩小增量
        gap //= 2

使用示例：

arr = [3, 7, 1, 9, 2, 8, 4, 6, 5]
shell_sort(arr)
print(arr)   # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

str_arr = ["pidancode.com", "Python", "希尔排序", "皮蛋编程"]
shell_sort(str_arr)
print(str_arr)   # 输出 ['Python', 'pidancode.com', '皮蛋编程', '希尔排序']

相关文章