python——資料結構之希爾排序

# coding:utf-8

def shell_sort(alist):
    """希爾排序"""
    # n=9
    n = len(alist)
    # gap =4
    gap = n // 2
    # i = gap
    # for i in range(gap, n):
    #     # i = [gap, gap+1, gap+2, gap+3... n-1]
    #     while:
    #     if alist[i] < alist[i-gap]:
    #         alist[i], alist[i-gap] = alist[i-gap], alist[i]

    # gap變化到0之前，插入算法執行的次數
    while gap > 0:
        # 插入算法，與普通的插入算法的差別就是gap步長
        for j in range(gap, n):
            # j = [gap, gap+1, gap+2, gap+3, ..., n-1]
            i = j
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        # 縮短gap步長
        gap //= 2


if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    shell_sort(li)
    print(li)