ML_algorithm/Sorting/shell_sort.py at master · luoshao23/ML_algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def shell_sort(lst):
    """
    shell sort
    """
    n = len(lst)
    gap = n // 2

    while gap:
        for i in range(gap, n):
            for j in range(i - gap, -1, -gap):
                if lst[j + gap] < lst[j]:
                    lst[j + gap], lst[j] = lst[j], lst[j + gap]
                else:
                    break
        gap //= 2

    # while gap:
    #     for i in range(gap, n):
    #         j = i
    #         while j > 0:
    #             if lst[j - gap] > lst[j]:
    #                 lst[j - gap], lst[j] = lst[j], lst[j - gap]
    #                 j -= gap
    #             else:
    #                 break
    #     gap //= 2


if __name__ == "__main__":
    lst = [5, 4, 7, 1, 12, 13, 23, 0, 4]
    print(lst)
    shell_sort(lst)
    print(lst)