python-036-插入排序

友好简单的排序算法——插入排序。直接看程序或者看定义之类直接讲解的文字，我觉得还是不太好理解。
其实插入排序更适合一部分已经有序的序列，比如1,2,3,4,5,6,9,8,7。

我们应该都摸过扑克牌吧，或者搓过麻将吧。我说的是实体的牌，不是换了斗地主还有麻将。
我们来回忆一下，当我们拿到一张新牌，我们在干什么？当我们拿到一堆没有序的牌我们在干什么？

我们在给牌排序，无论是从A，2，3，……，K，还是从2，A，K，Q，……3。我们总是从一张牌开始，然后拿到一张新的，放到它应该在的位置，直到我们全部排好我们的牌。

打麻将时，摸到一张新的牌，但是又不需要打出去时，我们也会把它放到它应该在的位置，我们在开始打麻将时就会把牌排好，直接插就行。

如果你没打过麻将，没有打过扑克，……，我也不知道怎么办了。

插入排序的原理和我们打扑克搓麻将是一样的。上面的两个例子，刚好就说明了我们的过程。两种，一是给一堆没有顺序的序列排序，二是给一个新的元素插入到一个有序的序列中。

我们把第一个元素看作一个有序的序列，后面的看作无序的待插入的序列。从第二个数开始，将其与其前一个数比较，如果不符合我们要求的排序顺序（升序或者降序，或者我们自己定义的规则），则互换位置，然后再与前一个数作比较直到满足我们的排序顺序。然后再将下一个数进行排序，直到全部完成。
例如 5, 3, 2, 6 的排序过程：

• 5, 3, 2, 6
• 3, 5, 2, 6
• 3, 5, 2, 6
• 3, 2, 5, 6
• 2, 3, 5, 6
• 2, 3, 5, 6
• 2, 3, 5, 6

这样就很好理解，但是还不够好。后面再来优化，我们先来实现这个insertion_sort():

def insertion_sort(a):
    for i in range(1,len(a)):   # 插入排序从第二个位置开始
        for j in range(i, 0, -1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]


a = [9, 7, 5, 6, 3, 2, 1, 4, 8]
insertion_sort(a)
print(a)

输出结果为：

image.png

这样一个简单的插入排序算法就实现出来了。

前面说的可以优化是这样，每一次排序时，我们都需要将当前值与其前面的数互换位置m次，m是比较后不满足要求的次数。所以如果第k个数需要排在第一位，那么他就需要互换位置k-1次。互换位置在python中直接用一个语句就可以完成，但是在其他的语言中就需要用一个临时值来做过渡，才能够完成，所以我们应该减少互换位置的次数。

我在前面的扑克牌的举例中，已经加粗了相关的部分，就是应该在的位置。我们先存储当前排序的数，然后找到它应该在的位置，然后将这个位置空出来，并把记录的值放到这个位置。也就是把这个位置之后的元素，都后移一个位置，然后插入，这真的是非常形象了。

下面我们来实现这个排序算法：

def new_insertion_sort(a):
    for i in range(1, len(a)):  # 插入排序从第二个位置开始
        cur = a[i]  # 保存当前的值
        j = i   # 用于寻找cur应该在的位置
        while j > 0:
            if a[j-1] > cur:
                a[j] = a[j-1]
                j -= 1
            else:
                break
        a[j] = cur

当然我们还可以改进：

def new_insertion_sort(a):
    for i in range(1, len(a)):  # 插入排序从第二个位置开始
        cur = a[i]  # 保存当前的值
        j = i   # 用于寻找cur应该在的位置
        while j > 0 and a[j-1] > cur:
            a[j] = a[j-1]
            j -= 1
        a[j] = cur

最后的结果是一样的：

image.png