一、原理
从排序序列的第二个元素开始，依次往前面查询，知道找到一个合适的位置就把它插进去。每个元素在交换完成之后 [0, n] 都是一个有序序列，它的时间复杂度为 O(n^2)。
排序逻辑：
|
1 2 |
for i in (1, n-1) 使用 data[i]前向查找，找到一个合适的位置插入 |
以下是对序列 [3, 7, 4, 1, 9, 6]的插入排序过程，初始时的状态为：
执行第一次插入 （从第二个元素开始），把 7 放到合适的位置：
执行第二次插入过程，把 4 放到合适位置：
执行第三次插入过程，把 1 放到合适位置：
执行第四次插入过程，把 9 放到合适位置：
执行最后一次插入过程，把 6 放到合适位置：
二、代码实现
1. C++实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void insert_sort(vector<int> &data){ auto length = data.size(); decltype(length) i, j, k; if (length < 2){ return; } int tmp; for (i = 1; i < length; i++){ tmp = data[i]; for (j = i; j > 0 && tmp < data[j - 1]; j--){ data[j] = data[j - 1]; } data[j] = tmp; } } |
2. python 实现
|
1 2 3 4 5 6 7 8 9 10 11 |
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 |