插入排序算法（C语言实现）

插入排序法的基本思想：在要排序的一组数中，假定前n-1个数已经排好序，现在将第 n 个数插到这个有序数列中，使得这 n 个数也是排好顺序的，如此反复循环，直到全部排好顺序。

对排序元素的前两个元素排序，然后将第 3 个元素插入已经排好序的两个元素中，这 3 个元素仍然是从小到大排序，接着将第 4 个元素插入，重复操作，直到所有的元素都排好序。

示例

使用插入排序法，按照从小到大的顺序对字符数组排序。C语言编程代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
/*插入排序法*/
void insert(char *arr,int count)
{
    int i,j;
    char temp;
    for(i=1;i<count;i++)
    {
        temp=arr[i];                          /*创建初值*/
        j=i-1;                                   /*开始位置*/
        while(j>=0 && temp<arr[j])        /*循环后移元素*/
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=temp;                      /*插入字符*/
        printf("第%d次交换结果:[%s]\n",i,arr);  /*输出交换后字符串*/
    }
}
int main()
{
    char array[MAX];
    int count;
    printf("输入将排序的字符串:\n");
    gets(array);
    count=strlen(array);
    insert(array,count);
    return 0;
}

运行结果：

输入将排序的字符串:
www.weixueyuan.net
第1次交换结果:[www.weixueyuan.net]
第2次交换结果:[www.weixueyuan.net]
第3次交换结果:[.wwwweixueyuan.net]
第4次交换结果:[.wwwweixueyuan.net]
第5次交换结果:[.ewwwwixueyuan.net]
第6次交换结果:[.eiwwwwxueyuan.net]
第7次交换结果:[.eiwwwwxueyuan.net]
第8次交换结果:[.eiuwwwwxeyuan.net]
第9次交换结果:[.eeiuwwwwxyuan.net]
第10次交换结果:[.eeiuwwwwxyuan.net]
第11次交换结果:[.eeiuuwwwwxyan.net]
第12次交换结果:[.aeeiuuwwwwxyn.net]
第13次交换结果:[.aeeinuuwwwwxy.net]
第14次交换结果:[..aeeinuuwwwwxynet]
第15次交换结果:[..aeeinnuuwwwwxyet]
第16次交换结果:[..aeeeinnuuwwwwxyt]
第17次交换结果:[..aeeeinntuuwwwwxy]

插入排序法就像按高矮排队一样，第 1 个人就是基准，然后插入第 2 个人。

如果插入的人较高，就将其排在第 1 个人的后面；如果插入的人较矮，先把第 1 个人后移 1 个位置，再把插入的人排在第 1 个位置。

在插入第 3 个人时，先把第 3 个人与第 2 个人比较，如果插入的人较高，就直接排在第 2 个人的后面。

如果插入的人较矮，则先把第 2 个人后移 1 个位置，然后第 3 个人与第 1 个人比较，如果插入的人较高，就直接排在第 2 个位置；如果插入的人较矮，先把第 1 个人后移 1 个位置，再把插入的人排在第 1 个位置，以此类推。

本例中，insert() 函数用双循环控制整个排序，其中外层循环控制是否还有待插入的字符，内层循环负责将待插入的字符排在合适的位置。

当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。