Insert Sort Algorithm in Python

最近在看《算法导论》，前面讲到插入排序，我第一反应，忘了这个算法是怎么样的，果然还是不够熟悉，那就再练习几次。

这个算法还是非常重要的，很多语言的库里面，sort函数的实现，当个数小于某个较小的数时，都会使用插入排序，那是因为插入排序在元素有序的情况下，时间复杂度是$O(n)$, 而快排是$O(n^2)$，在元素较少的情况下，列表有序的概率比较大，比如1个元素是100%, 2个元素是50%, 3个元素是$\dfrac{1}{6}$，所以，在元素较少的情况下，使用插入排序来进行排序，速度是非常快的。

遇到这个算法，就想起打牌就行了。一开始我们左手是没有牌的，拿到一张牌，放到左手，第二张，从后面往前面比较，直到找到一张比它小的牌或者到了最前面，然后插入那个位置。

def insert_sort(arr):
    for i in range(1, len(arr)):
        j = i - 1
        # 临时记下要插入的元素
        temp = arr[i]
        # 找到比它小的元素
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        # 插入在比它小的元素的后面
        arr[j + 1] = temp
        print(arr)
        
arr = [5, 2, 4, 6, 1, 3]
print(arr)
insert_sort(arr)

[5, 2, 4, 6, 1, 3]
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6]