希尔排序算法是一种分组插入排序算法,是一种更高效的插入排序算法。和普通的插入排序算法相比,希尔排序算法减少了移动元素和比较元素大小的次数,从而提高了排序效率。

实现思路

1)取第一个整数d1=n//2,将元素分为d1个组,每组相邻量元素之间的距离为d1,在各组内进行直接插入排序;

2)取第二个整数d2=d1//2,重复上述分组排序过程,直到di=1,即所有元素在同一组内进行直接插入排序。

希尔排序每趟并不是某些元素有序,而是使整体数据越来越接近有序,最后一趟排序使所有数据有序。

代码示例

def shell_sort(arr, gap):
    if gap == 0:
        return
    for i in range(gap, len(arr)):
        pos = i - gap
        temp = arr[i]
        while pos >= 0 and arr[pos] > temp:
            arr[pos + gap] = arr[pos]
            pos -= gap
        arr[pos + gap] = temp
    # 递归间隔折半
    gap //= 2
    shell_sort(arr, gap)

lst = [27, 13, 35, 10, 3, 33]
shell_sort(lst, len(lst) // 2)
print(lst)

本文为 陈华 原创,欢迎转载,但请注明出处:http://www.ichenhua.cn/read/259