基本思想： 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序
#include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> arr{ 3,34,4,12,5,2}; cout << "原数组:" << endl; print(arr); //插入排序 for (int i = 1; i < arr.size(); i++) { int temp = arr[i]; int j; for ( j = i; j >0&&arr[j-1]>temp; j--) { arr[j] = arr[j - 1]; } arr[j] = temp; } cout << "排序后：" << endl; print(arr); system("pause"); }时间复杂度分析：
最好的情况，本身就是有序的，那么比较次数就是每个arr[i]和arr[i-1]比较，共比较了次，由于是有序的，每次都不用移动，时间复杂度为O（n），
最坏的情况：待排序表是逆序的情况，此时需要比较，记录移动的次数也达到了最大值次。
如果排序记录是随机的，那么根据概率相同的情况，平均比较次数和移动次数约为次。因此，我们得出直接插入排序法的时间复杂度为O（n方）,从这里可以看出，同样的O（n方）时间复杂度，直接插入排序法，比冒泡和选择的效果好。
