希尔排序
    Screen Shot 2021-12-01 at 8.08.22 PM.png
    动画很神奇

    2. def insert_sort_gap(li,gap):  ## 可以把之前的插入排序认为默认gap是1
    3.     for i in range(gap,len(li)):
    4.        j = i -gap ## 有序区，从0开始
    5.        tmp = li[i]
    6.        while j >=0 and li[j] >tmp:
    7.            li[j+gap] = li[j]
    8.            j -=gap
    9.        li[j+gap]=tmp
    10. def shell_sort(li):
    11.     d = len(li)//2
    12.     while d >=1:
    13.         insert_sort_gap(li,d)
    14.         d = d//2
    16. li = list(range(1000))
    17. import random
    18. random.shuffle(li)
    19. shell_sort(li)
    20. print(li)

    之前写过插入排序的话，写起来耶很容易，把之前的插入排序认为默认gap是1的话，理解起来，也很容易 通过不断局部有序，然后扩大局部，让整体有序
    取gap的方法有很多，很有趣，可以google
    计数排序Screen Shot 2021-12-01 at 8.52.35 PM.png

    1. def count_sort(li,max_count=100):
    2.     count = [0 for _ in range(max_count+1)]
    3.     for val in li:
    4.         count[val] +=1 ## pretty cleaver
    5.     li.clear()
    6.     for ind,val in enumerate(count):
    7.         for i in range(val):
    8.             li.append(ind)
    10. import random
    11. li = [random.randint(0,100) for _ in range(1000)]
    12. print(li)
    13. count_sort(li)
    14. print(li)

    有很多限制，比如，不知道最大值，或者值跨度特别大（废空间）
    桶排序
    Screen Shot 2021-12-02 at 5.48.12 PM.png