#include<iostream>
using namespace std;
void print(int a[], int n)
{
for(int j= 0; j<n; j++)
{
cout<<a[j] <<" ";
}
cout<<endl;
}
void insertSort(int a[], int n)
{
for(int i = 1; i < n; i++) //第一个元素作为基准元素，从第二个元素开始把其插到正确的位置
{
if(a[i] < a[i-1]) //如果第i个元素比前面的元素小
{
int j = i-1; //需要判断第i个元素与前面的多个元素的大小，换成j继续判断
int x = a[i]; //将第i个元素复制为哨兵
while(j >= 0 && x < a[j]) //找哨兵的正确位置，比哨兵大的元素依次后移
{
a[j+1] = a[j];
j--;
}
a[j+1] = x; //把哨兵插入到正确的位置
}
}
}
int main()
{
int a[10] = {8,1,9,7,2,4,5,6,10,3};
cout<<"初始序列：";
print(a,10);
insertSort(a,10);
cout<<"排序结果：";
print(a,10);
system("pause");
}
来源：https://blog.csdn.net/yangchuang93/article/details/80861669
---------------------
1.从第一个元素开始，该元素可以认为已被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一个位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后，重复2~5
虽然是一个很简单的插入排序，但是这个方法的用途很广，也很实用。诸如游戏里的一键整理背包，按照稀有度来排序就是按照这种思想进行的。
插入排序有几种方法 
各个排序方法分不同的场合，考虑到效率等种种问题 ，选择最优的方法使我们所追求的。