继续新生开学老师按照学生身高排列队伍的话题，除了冒泡排序之外，老师还有另外一种选择……

插入排序是通过 分堆 的方式逐渐的把未排序的元素插入到已排序的元素中去的算法。

算法过程

使用插入排序首先要确定一个初始的有序的队列。对于站队来说，最开始能确定的有序的队列就是只包含一个同学的队列，这个肯定是有序。然后依次的把没有归到队伍中的同学依次的叫过来排进队列，每排一个，就要保证排进去之后，队伍是有序的，直到所有的同学都被排到了队伍中，所有的同学就站队完毕。

还是那一批同学：150 165 160 173 155。

• 1、所有同学都站到一边，150 同学出来站到另外一边（此时150同学自己一个队伍，这个队伍是有序的，因为只有他自己）。
• 2、下一个没排序的队列（剩余的165 160 173 155）中的 165 同学过来站到这边排好序的队列（只有150同学一人的队列） 最后面，也就是 150 同学后面，然后比较一下，165 比 150高，所以，165 就站到 150 的后面；此时，就已经有了两个同学排队完毕：150 165。
• 3、下一个没排序的队列（剩余的160 173 155）中的 160 同学过来，站到这边排好序的队列（150 165）的后面。开始比较，160 同学比165同学矮一点，所以，160 同学和 165 同学调换位置，也就是 160 同学站到 165 同学的前面去，此时队伍变成了 150 160 165; 再次比较 160 同学和他前面的 150 同学，发现 160 比 150 要高，所以，不交换俩人的位置。此时已经比较到了队列的最前面，也就是整个队列比较完了，之前有序的队列：150 165，现在又变成了有序队列：150 160 165（新过来的同学被安排到了合适的位置上去）。
• 4、下一个没排序的队列（173 155）中的 173 同学……（重复3的步骤）
  ……
  最终当无序队列中的同学一个个的都被插入到了另外一个已经有序的队列中，且插入之后有序序列依然有序，最终的结果就是，我们已经在这个过程中完成了整只队伍的排序，全班的所有同学都站好了队，整只队伍是按照身高排好序了的。

插入排序过程.png

算法实现

#coding:utf-8

import numpy as np 

def insertion_sort(data):
    if len(data) < 2:
        return data

    data_len = len(data)

    for i in range(1, data_len, 1):
        value = data[i]
        # 比较并且向后移动的过程
        j = i-1
        while j >= 0:
            if data[j] > value:
                data[j+1] = data[j]
                j -= 1
            else:
                break
        data[j+1] = value
    
array = np.arange(20)
np.random.shuffle(array)
array = list(array)
print('输入的数据: {}'.format(array))
insertion_sort(array)
print('排序之后的数据：{}'.format(array))

结果：

插入排序结果.png


上一篇：写给媳妇儿的算法（四）——冒泡排序
上一篇：写给媳妇儿的算法（六）——快速排序