转载请注明出处：http://blog.csdn.net/ruoyunliufeng/article/details/26059615
插入排序：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
一.插入排序算法
/***************************************************************
*版权所有 (C)2014,公司名称。
*
*文件名称：插入排序法
*内容摘要：无
*其它说明：无
*当前版本：V1.0
*作 者：若云流风
*完成日期：2014.5.17
***************************************************************/
#include <stdio.h>
#define N 7
void disp(void);
int a[N]={5,0,7,1,12,11,9};
/*排序函数*/
void InsertionSort(void)
{
int j,p,temp;
for(p=1;p<N;p++)
{
temp=a[p]; //a[p]和左面的有序数列去比较
/*j>0保证不溢出，因为当j=0时啊a[j-1]非法，用a[p]分别与左面的值相比较
**如果a[p]小的话则互换位置，
*/
printf("\n\n排序过程: ");
for(j=p; j>0 && a[j-1]>temp;j--)
{
a[j]=a[j-1];
disp();
}
a[j]=temp;
printf("\n\n新一轮排序结果: ");
disp();
}
}
/*输出函数*/
void disp(void)
{
int i;
// printf("\n排序结果: \n");
printf("\n\n");
for(i=0;i<N;i++)
{
printf("%d", a[i]);
printf(" ");
}
}
int main(void)
{
InsertionSort();
// disp();
return 0;
}
二.算法会说话
1.结果输出
2.结果分析
上图就是每一轮的排序过程和结果。对于7个数的数组，共需要6轮。现在我拿出第三轮来详细讲解这个插入排序。
程序在第二轮已经将前三个数排好了，第三轮将a[3]（也就是第四个数）与前面的数相比较。1与7比较，确实比7小所以a[3]被赋值为7,然后1继续向左走，1比5小，a[2]被赋值为5，然后1继续向左走，1比0大，循环终结。将a[1]赋值为1（也就是temp）。