前两篇中，无论是冒泡排序还是快速排序，他们的核心思路都是“交换”，通过一系列的“交换”过程，使得数据有序归位。除了基于交换类的排序，常见的还有插入类的排序，例如直接插入排序。

直接插入排序的思想也很“直接”：每次排序将一个待排序的元素作为关键字，将这个关键字按照顺序插入前面已经有序的元素序列中，直到插入完成。

一般情况下的做法是，从第一个元素开始，此时第一个元素便是有序序列的唯一元素，然后将第二个元素插入这个“有序序列”，然后第三个，以此类推即可。

于是用Python3的方法很容易实现，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

def insert_sort(lists):
    """直接插入排序"""
    length = len(lists)
    for i in range(1, length):
        temp = lists[i]
        j = i - 1

        while j >= 0 and lists[j] > temp:
            lists[j + 1] = lists[j]
            j -= 1
        lists[j + 1] = temp
    return lists

可以看出，先是在有序序列中找到不大于关键字的位置，然后将关键字插入，在插入的这一过程中，依然是基于交换的，但由于该算法的基本思想是一次次的插入，所以一般不归为交换类排序。

随机生成10000个数测试一下，结果如下图所示：

结果显示直接插入排序只是比冒泡排序略快一点而已，比快速排序要慢很多，更不用和sorted方法比了。

分析直接插入排序的时间复杂度：

1. 考虑最坏的情况，整个原始序列是逆序的，则每次内层循环都要完整执行一遍，总的执行次数达到n(n-1)/1，所以时间复杂度是O(n²)；
2. 最好的情况是原始序列本身有序，则内层循环不执行，所以时间复杂度是O(n)。

综合两种请情况来看，直接插入排序的时间复杂度为O(n²)，并不是一种高效的算法，但是其实现相对简单，适用于小规模的数据处理。

在上面的实现中，不会对相同的值做交换，因此这种插入排序的实现是稳定的。