C 语言插入排序算法及实例代码
插入排序是排序算法的一种，它不改变原有的序列（数组），而是创建一个新的序列，在新序列上进行操作。
这里以从小到大排序为例进行讲解。
基本思想及举例说明
插入排序的基本思想是，将元素逐个添加到已经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。
在实际使用中，通常是排序整个无序数组，所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时，将第一个元素作为排序好的子数组，插入第二个元素；第二轮，将前两个元素作为排序好的数组，插入第三个元素。以此类推，第i轮排序时，在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。
下面，以对3 2 4 1进行选择排序说明插入过程，使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。
第1轮
[3] [2 4 1] （最初状态，将第1个元素分为排序好的子数组，其余为待插入元素）
[3] [2 4 1] （由于3>2，所以待插入位置j=1）
[2 3] [4 1] （将2插入到位置j）
第2轮
[2 3] [4 1]（第1轮排序结果）
[2 3] [4 1]（由于2<4，所以先假定j=2）
[2 3] [4 1]（由于3<4，所以j=3）
[2 3 4] [1]（由于4刚好在位置3，无需插入）
第3轮
[2 3 4] [1]（第2轮排序结果）
[2 3 4] [1]（由于1<2，所以j=1）
[1 2 3 4] （将1插入位置j，待排序元素为空，排序结束）
算法总结及实现
选择排序对大小为N的无序数组R[N]进行排序，进行N-1轮选择过程。首先将第1个元素作为已经排序好的子数组，然后将剩余的N-1个元素，逐个插入到已经排序好子数组；。因此，在第i轮排序时，前i个元素总是有序的，将第i+1个元素插入到正确的位置。
#include<stdio.h>
#include<stdlib.h>
#defineN8
voidinsert_sort(inta[],intn);
//插入排序实现,这里按从小到大排序
voidinsert_sort(inta[],intn)//n为数组a的元素个数
{
//进行N-1轮插入过程
for(inti=1;i<n;i++)
{
//首先找到元素a[i]需要插入的位置
intj=0;
while((a[j]<a[i])&&(j<i))
{
j++;
}
//将元素插入到正确的位置
if(i!=j)//如果i==j，说明a[i]刚好在正确的位置
{
inttemp=a[i];
for(intk=i;k>j;k--)
{
a[k]=a[k-1];
}
a[j]=temp;
}
}
}
intmain()
{
intnum[N]={89,38,11,78,96,44,19,25};
insert_sort(num,N);
for(inti=0;i<N;i++)
printf("%d",num[i]);
printf("\n");
system("pause");
return0;
}
注意：插入排序是一种稳定的排序算法，不会改变原有序列中相同数字的顺序。
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
以上就是对插入排序的详细介绍，希望能帮助C语言开发的同学理解掌握插入排序。