希尔排序算法

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

实现思路

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)