排序算法一：插入排序

一、原理

从排序序列的第二个元素开始，依次往前面查询，知道找到一个合适的位置就把它插进去。每个元素在交换完成之后 [0, n] 都是一个有序序列，它的时间复杂度为 O(n^2)。

排序逻辑：

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

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

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

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

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

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

二、代码实现

1. C++实现

2. python 实现