插入排序：
类似于玩扑克牌抓牌的动作
从一个待排序的数组中拿出一个数字插入到一个已排好序的数组中，使得已排好序的数组仍是个有序的数组
代码如下：
//插入排序 void insert_sort(int unsort[], int length) { cout<<"插入排序："<<endl; //从第二个数开始进行插入 for(int i = 1; i < length; i++) { if(unsort[i]<unsort[i-1]) { int temp = unsort[i];//哨兵元素 int j = i; //查找在有序表的插入位置 while(j >0 && unsort[j-1]>temp) { unsort[j]=unsort[j-1]; j--; //元素后移 } unsort[j] = temp; //插入到正确位置 } cout<<"第"<<i<<"趟:"; for(int k = 0; k < length; k++) { cout<<unsort[k]<<" "; } cout<<endl; } }
注意：
1.从第二个数字开始
2.待排序的数字是个哨兵元素，用哨兵元素与排好序的元素从后往前进行对比，数字比哨兵元素大则该数字后移，直到找到第一个比哨兵元素小的，插入到该位置。
运行结果如下：
原文：http://www.cnblogs.com/JuneXiangBlogs/p/5283001.html