程序员必须掌握的数据结构：希尔排序 python代码实现

希尔排序，时间复杂度在O(n)~O(n^2)之间，也可以认为是O(n^3/2)，相对于插入排序的改进，比较和偏移量更少，从而每次传递都会产生更“整洁”的子列表。 12行，其中5行用于增加，7行用于插入。

# 源码: https://github.com/SpikeKing/data_structure_with_python
def shell_sort(alist):
    """
    希尔排序
    1. 两部分，第1部分，计算增量gap和起始位置s_pos；
    2. 增量是累除2，s_pos是增量的遍历
    3. 增量插入排序，额外传入起始位置和增量；
    4. range的起始由起始位置+增量；
    5. 循环条件为大于等于增量，差值为增量
    6. 12行，增量部分5行，插入部分7行
    :param alist: 待排序alist
    :return: None
    """
    gap = len(alist) // 2
    while gap > 0:
        for s_pos in range(gap):
            insert_sort_gap(alist, s_pos, gap)
        gap = gap // 2


def insert_sort_gap(alist, s_pos, gap):
    """
    带增量的插入排序
    :param alist: 待排序alist
    :param s_pos: 起始位置
    :param gap: 增量
    :return: None
    """
    for i in range(s_pos + gap, len(alist), gap):
        cur_val = alist[i]
        pos = i
        while pos >= gap and alist[pos - gap] > cur_val:
            alist[pos] = alist[pos - gap]
            pos -= gap
        alist[pos] = cur_val


def test_of_shell_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    shell_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_shell_sort()