插入排序

• 伪代码如下

INSERTION_SORT
for j = 2 to A.length:
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key:
          A[i+1] = A[i]
          i = i - 1
    A[i+1] = key

插入排序像抓扑克牌，左手的牌可以看作是已经有序，从桌面上每抓一张都跟左手的拍比较，可以从左往右比，也可以从右往左比，这决定是降序排列还是升序排列。

1. 抓第一张拍，左手无牌，认为有序，A[1]插入左手，即从A[2]开始。
2. key = A[j]表示，抓的牌要插入左手，势必会占用一个牌位。如果不赋值给第三变量，插入后，已经有序的牌会向右移，占据此位，原始数据便丢失。其二，便于跟合适的位置A[i+1]交换（插入）牌位。
3. i = j - 1以及while循环语句是A[j]与A[j-1]之前以此比较，即桌面抓上来的牌一张一张跟左手的比较。发现抓的牌比左手最右边的牌小就继续向左移动、比较，直到找到最合适的位置。
4. A[i+1] = A[i]，表示，抓起来的牌比左手最右边的牌小，便赋值给抓起来的牌位，即A[i+1]，i = i - 1，开始下一张对比，直到最左边，即i > 0，退出循环。
5. A[i] < key 则是降序输出。

• python实现代码如下：

arthur@arthur:~/Documents/learn_pyProject$ vim  insertion_sort.py 
def insertion_sort(sl):
    for j in range(1, len(sl)):
        key = sl[j]
        i = j - 1
        while i >= 0 and sl[i] > key:
            sl[i+1] = sl[i]
            i = i - 1
        sl[i+1] = key

    return sl

before_sort = [5, 2, 4, 6, 1, 3]
print('before_sort:')
print(before_sort)
print('after_sort')
print(insertion_sort(before_sort))


arthur@arthur:~/Documents/learn_pyProject$ python insertion_sort.py 
before_sort:
[5, 2, 4, 6, 1, 3]
after_sort
[1, 2, 3, 4, 5, 6]