插入排序算法

插入排序算法从字面上的理解就是把数据插入到一个已经排好序的队列中。朴素一点理解，就是在那里已经站了一排人，从矮到高排的，现在有一个人要按高矮排这个队列里。那应该插入到哪个位置呢，不知道啊，那就从最高的位置开始比较，一个个往前比较，然后插入到合适的位置。

算法的关键点：

1. 把数插入到一个已排好的队列中，从后往前开始比较。
2. 如果当前的数据大于比较大的数，把数往后移动一个位置。

插入排序算法是稳定性的排序算法，时间复杂度是o(n^2)。

看一个简单的例子：

5， 3， 2， 1 一趟插入排序是如何进行

插入排序算法，第一个数认为是已经排好序的，从第二数 3 开始。

开始比较时， tmp = 3， i = 1 记录当前的值与下标

第一次比较： 5， 3， 2， 1；3比5小， 把5移动到3的位置。

此时5留出了一个空位置 j = 0，而前面没有数据了。

把3插入到j = 0 位置的，就会得到第一趟插入排序的算法的结果： 3,5,2,1。

第二趟排序从下一个位置开始，重复上一次的过程，一直到数组的最后。

下面我们看一下算法的代码实现:

def insert_sort(elements):
    n = len(elements)
    for i in range(1, n):
        tmp = elements[i]
        k = i
        for j in range(i, 0, -1):
            if tmp < elements[j - 1]:
                elements[j] = elements[j - 1]
                k = j - 1
            else:
                break
        elements[k] = tmp


if __name__ == '__main__':
  arr = [5, 2, 3, 1]
  insert_sort(arr)
  print(arr)

复制

运行后输出结果：

[1, 2, 3, 5]