一、原理

从排序序列的第二个元素开始，依次往前面查询，直到找到一个合适的位置就把它插进去。

每个元素在交换完成之后[0, n]都是一个有序序列，它的时间复杂度为O(n^2)。

最好的情况下，序列有序，时间复杂度为O(n)。

最坏的情况下，序列逆序，时间复杂度为O(n^2)。随机的情况下平均时间复杂度接近于最坏的情况。

排序逻辑：

for i in (1, n-1)
    使用data[i]前向查找，找到一个合适的位置插入

以下是对序列[3, 7, 4, 1, 9, 6]的插入排序过程，初始时的状态为：

执行第一次插入（从第二个元素开始），把7放到合适的位置：

执行第二次插入过程，把4放到合适位置：

执行第三次插入过程，把1放到合适位置：

执行第四次插入过程，把9放到合适位置：

执行最后一次插入过程，把6放到合适位置：

二、代码实现

2.1 c++实现

基于模板的实现：

template<typename T>
static void insert_sort(vector<T> &v) {
    size_t i, j;
    T key;

    if (v.size() < 2)
        return;

    // 从第二个元素开始插入
    for (i = 1; i < v.size(); i++) {
        // 备份当前元素
        key = v[i];
        // 依次往前查找合适的位置
        for (j = i; j > 0 && key < v[j - 1]; j--) {
            v[j] = v[j - 1];
        }
        // 给当前位置赋值
        v[j] = key;
    }
}

单元测试：

TEST(insert_sort, multi_element) {
    int i, j;
    vector<int> v(SORT_ELE_COUNT);
    for (i = 0; i < TEST_CASE_COUNT; i++) {
        // 产生随机数
        for (j = 0; j < SORT_ELE_COUNT; j++) {
            v[j] = (int)rand() % 1000000;
        }

        // 排序
        insert_sort(v);

        // 检测
        for (j = 1; j < SORT_ELE_COUNT; j++) {
            EXPECT_GE(v[j], v[j - 1]);
        }
    }
}

2.2 python实现

def insert_sort(data):
    size = len(data)
    if size < 2:
        return
    for i in range(1, size):
        tmp = data[i]
        j = i
        while j > 0 and tmp < data[j - 1]:
            data[j] = data[j - 1]
            j -= 1
        data[j] = tmp

2.3 c语言实现

2019-04-21添加：复习数据结构，添加c语言版。

void insert_sort(int *data, unsigned int len) {
    int tmp;
    unsigned int i, j;

    for (i = 1; i < n; i++) {
        tmp = data[i];
        for (j = i; j > 0 && tmp < data[j - 1]; j--)
            data[j] = data[j - 1];
        data[j] = tmp;
    }
}