插入排序类似于扑克牌摸牌的过程（我的习惯），小的放在前面，如果抓到更小的就再往前面放
但是第一张是不用排的。。。。
数组： 3, 6, 2, 1, 9
->2,3,6,1,9
->1,2,3,6,9
#include <iostream>
using namespace std;
int main()
{
int a[] = { 3, 6, 2, 1, 9 };
int key, j;
for (int i = 1; i < sizeof(a) / 4; i++)
{
key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
for (int i = 0; i < sizeof(a)/4; i++)
{
printf("%d ", a[i]);
}
cin.get();
}
当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。
所以，数据越接近正序，直接插入排序的算法性能越好。
空间复杂度为O(1);
稳定
原文：http://www.cnblogs.com/xiaoma123/p/5220084.html