插入排序算法，C语言插入排序算法详解

插入排序的算法特别好理解，与我们的日常生活紧密相连，或者说它来源于对日常生活的感悟。插入排序也是用得最多的一种排序方法。但原因不是因为它好理解，而是因为在实际编程中数据往往都是已经排好序的，所以一般都是往排好序的序列中按顺序插入一个数据。此时用插入排序就会特别快。

那么插入排序到底是怎样的呢？比如有十个人从左往右无序地排列，现在要你按身高从低到高排列，你会怎么排？

首先第二个人和第一个人比，如果第二个人比第一个人矮，那么它们互换位置，否则不动，此时前两个人的顺序就排好了；然后第三个人再与前两个已经排好的比，怎么比？第三个人先站出来，看看前面在哪个位置中自己比左边的高比右边的矮，然后就插进去，如果自己与前面的人相比是最高的，那么就不动，此时前三个人的顺序就排好了……就这样一直往后比较。

那么怎么找比左边高比右边矮的那个位置呢？因为左边都是已经排好序的，所以依次与左边的比，直到遇到一个比他矮的，那么那个位置就是比左边高比右边矮的位置。如果没找到一个比他矮的那么他就是最矮的，那么他就排在最左边。那么是怎么插入的呢？因为每个与左边一个一个比较的那个人都是先站出来的，所以他的那个位置是空的。这时在找到比他矮的那个人之前，每比完一个，与他进行比较的那个人就往右挪一个位置，将空依次补上。直到找到比他矮的人，那时比他矮的那个人的前面就空出了一个位置，然后他就可以插进去。所以在程序中要先用一个变量保存这个“站出来的”数。

下面来写一个插入排序的算法实现从小到大排序。

# include <stdio.h>
int main(void)
{
    int i, j;
    int temp;  //用于存储站出来的数
    int a[] = {900, 2, 3, -58, 34, 76, 32, 43, 56, -70, 35, -234, 532, 543, 2500};
    int n = sizeof(a) / sizeof(a[0]);  //存放数组a中元素的个数
    for (i=1; i<n; i++)  /*i从1开始, 即从第二个人开始比, 每循环一次比较一轮*/
    {
        temp = a[i]; 
        j = i - 1;  //与它前一个数比较
        while ((j>=0) && (a[j]>temp))  /*与左边所有人都比完了或找到一个比他矮的为止*/
        {
            a[j+1] = a[j];  //与他比完之后比它高的向右挪一个位置
            --j;  /*最经典的地方, 每次减1, 再与前一个比较, 直到与左边所有的都比完或比到有一个数小于等于它为止, while循环退出, 此时左边形成一个新的有序序列*/
        }
        if (j != i-1)  /*这句也很经典, j != i-1说明执行过上面的while, 并且找到位置了, 那么就插进去；如果j = i-1, 则说明没有执行过while, 说明他和左边的相比是最高的, 则不用换位置*/
        {
            a[j+1] = temp;  /*之所以j要加1是因为while在退出之前又执行了一次--j*/
        }
    }
    for (i=0; i <15; ++i)
    {
        printf("%d\x20", a[i]);
    }
    printf("\n");
    return 0;   
}

输出结果是：-234 -70 -58 2 3 32 34 35 43 56 76 532 543 900 2500

总结

冒泡排序是从左往右比，而插入排序是从右往左比，但也是一轮一轮地比较。原序列中从左边第二个数开始，每轮比较一个数。每个数依次与它左边的所有数相比较，左边的都是已经排好的序列，该数与这些排好的序列逐个比较，然后插入其中，形成一个新的排好的序列。

从程序中也可以看出，如果是将一个数据插入已经排好的序列中，使用插入排序无疑是最好的选择。此时计算量只不过是冒泡排序的一轮比较而已。比如向序列“1 3 4 5 7 9 11 13 20”插入一个 6，用插入排序就非常简单了。程序如下：

# include <stdio.h>
int main(void)
{
    int a[10] = {1, 3, 4, 5, 7, 9, 11, 13, 20};
    int i = 8;  //存储数组有效数据的最大下标
    int data = 0;  //存储要插进来的数
    printf("请输入要插进来的数:");
    scanf("%d", &data);
    while ((i>=0) && (a[i]>data))  /*找到data应该插入的位置, 并把那个位置空出来*/
    {
        a[i+1] = a[i];
        --i;
    }
    a[i+1] = data;  //将data插入那个位置
    for (i=0; i<10; ++i)
    {
        printf("%d\x20", a[i]);
    }
    printf("\n");
    return 0;   
}

输出结果是：
         请输入要插进来的数:6
         1 3 4 5 6 7 9 11 13 20

需要注意的是，前面的程序中数组的长度都没有手动指定，而上面这个程序是手动指定了数组的长度为 10。这是为什么？

这是因为，如果不手动给定还是写成“int a[]={1，3，4，5，7，9，11，13，20};”这种形式的话，那么系统就会根据初始化数据的个数认为该数组的长度为 9。但是现在要往该数组中插入一个元素，那么数组的长度至少是 10，不然插入数据后，数组的最后一个元素就会向后覆盖一个 int 型的未分配给它的内存空间。

所以为了避免这种情况的发生，就只能手动指定数组的长度。但是这样的话就意味着不能再通过 sizeof(a)/sizeof(a[0]) 来计算数组中存放的有意义的数据的长度，因为 sizeof(a)/sizeof(a[0]) 计算的是数组的总长度。这也就意味着只能通过手动的方式指定数组中存放有意义的数据的元素的最大下标 i。

综上所述，这种情况就需要程序员自己手动维护数组的长度。这也从某一方面体现出了数组的缺陷，即它无法动态地扩充长度。动态数组和链表就不存在数组的这个缺陷，这两种结构后续会讲。