插入排序算法

和前面介绍的冒泡排序算法、选择排序算法类似，插入排序算法也是一种基础排序算法，其时间复杂度也是O(n^2)。实现思路是：从当前位置开始，从后往前遍历其之前的序列，如果比当前位置的值大，则往后挪动一位，直到遇见比其小的位置结束。

举个例子

用插入算法对 [33, 14, 27, 10, 35] 实现升序排序过程如下：

1) 14和 [33] 比较，33比14大，所以33往后挪动一位；

[14, 33, 27, 10, 35]

2) 27和 [14, 33] 比较，33比27大，所以33往后挪动一位，但14比27小，这一轮结束；

[14, 27, 33, 10, 35]

3) 10和 [14, 27, 33] 比较，33、27、14都比10大，全部往后挪动一位；

[10, 14, 27, 33, 35]

4) 35和 [10, 14, 27, 33] 比较，33比35小，本轮结束。

[10, 14, 27, 33, 35]

代码示例

def insert_sort(lst):
    for i in range(1, len(lst)):
        pos = i - 1
        temp = lst[i]
        while pos >= 0 and lst[pos] > temp:
            lst[pos + 1] = lst[pos]
            pos -= 1
        lst[pos + 1] = temp

lst = [33, 14, 27, 10, 35]
insert_sort(lst)
print(lst)