C语言插入排序算法（附带完整实现源码）

插入法排序较为复杂，其基本原理是抽出一个数据，在前面的数据中寻找相应的位置并将其插入，直到完成排序。

下面以数字 9、6、15、4、2 为例，介绍采用插入法实现将数字按从小到大的顺序进行排列，如下图所示。


从图 1 可以发现，插入法排序的过程如下：

• 第 1 次排序将第 1 个数 9 取出来，并放置在最前面；
• 取出第 2 个数 6，因为 6 小于 9，所以将 6 放在 9 之前；
• 然后取出下一个数 15，先用 15 和 9 比较，因为 15 比 9 大，所以将 15 放在 9 的后面。

以此类推，不断取出未进行排序的数字并将其与排好序的数字进行比较，然后将其插入相应的位置，直到将一组数字按从小到大的顺序排列为止。

下面通过实例来介绍如何通过程序使用插入法实现数组元素按从小到大的顺序排列。

【实例】声明了一个整型数组和两个整型变量，其中整型数组用于存储用户输入的数字，而两个整型变量分别作为两个元素交换时的中间变量和记录数组元素位置的变量，然后通过双层循环进行插入法排序，最后将排好序的数组进行输出。

具体代码如下：

#define _CRT_SECURE_NO_WARNINGS                /*解除vs安全性检测问题*/
#include <stdio.h>                             /*包含头文件*/
int main()                                     /*主函数main()*/
{
   int i;                                      /*定义变量*/
   int a[10];
   int iTemp;
   int iPos;
   printf("输入数据：\n");                      /*提示信息*/
   for (i = 0; i<10; i++)                       /*输入数据*/
   {
          printf("a[%d]=", i);
          scanf("%d", &a[i]);
   }

   /*从大到小排序*/
   for (i = 1; i<10; i++)                           /*循环数组中的元素*/
   {
          iTemp = a[i];                             /*设置插入值*/
          iPos = i - 1;
          while ((iPos >= 0) && (iTemp<a[iPos]))    /*寻找插入值的位置*/
          {
                 a[iPos + 1] = a[iPos];             /*插入数值*/
                 iPos--;
          }
          a[iPos + 1] = iTemp;
   }

   /*输出数组*/
   for (i = 0; i<10; i++)
   {
          printf("%d\t", a[i]);                     /*输出制表符*/
          if (i == 4)                               /*如果是第5个元素*/
                 printf("\n");                      /*输出换行符*/
   }
   printf("\n");

   return 0;                                        /*程序结束*/
}

运行程序，结果为：

输入数据：
a[0]=12
a[1]=8
a[2]=36
a[3]=26
a[4]=43
a[5]=10
a[6]=89
a[7]=25
a[8]=65
a[9]=3
3       8       10      12      25
26      36      43      65      89