1、直接插入排序：
从第二个元素开始，与前面的元素做比较，小则插到前面去。
直接插入排序属于稳定性排序：关键词相同的数据元素将保持原有位置不变，（关键在于指定下标必须要小于判断值才做位置变化，当出现两个相同的数据时，并不会交换位置）
实现步骤：
- 已知列表a，从第二个元素开始，下标记为i ，将i对应的值保存在临时变量tmp 中；
- 将 i 的前一个元素记录为 j ，j = i - 1；
- 判读 j 的值和 i 的值的大小，如果tmp < list[j] 的值，则将 j 往后挪，也就是 list[j+1] = list[j]， 同时 j的下标向前移动 继续做与 tmp 的值的判断。
- 直到 tmp 不小于 list[j]， 将tmp 放到 list[j + 1] 中。
2、复杂度
时间复杂度：O(n²)
空间复杂度：O(1)
3、稳定性：稳定排序
当元素小于前一个数据才向前插入，当出现相同的数据时，是不小于的，所以为稳定排序。
4、例子：
#include <iostream>
using namespace std;
// 直接插入
int main() {int list[8] = {45, 38, 66, 90, 88, 10, 25, 45};int len = sizeof(list)/sizeof(list[0]);for (int i = 1; i < len; i++) {int tmp = list[i], j = i - 1;while (j >= 0 && tmp < list[j]) {list[j+1] = list[j];j--;}list[j+1] = tmp;cout<<i<<"次排序后：";for (int a = 0;a < len;a++) {cout << list[a] << " ";}cout<<endl;}cout<<"最后结果：";for (int i = 0;i < len;i++) {cout << list[i] << " ";}return 0;
}输出结果：
1次排序后：38 45 66 90 88 10 25 45
2次排序后：38 45 66 90 88 10 25 45
3次排序后：38 45 66 90 88 10 25 45
4次排序后：38 45 66 88 90 10 25 45
5次排序后：10 38 45 66 88 90 25 45
6次排序后：10 25 38 45 66 88 90 45
7次排序后：10 25 38 45 45 66 88 90
最后结果：10 25 38 45 45 66 88 90参考：
百度百科——排序算法：百度百科-验证
生命不息，学习不止，若有不正确的地方，欢迎指正。
