插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序 法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为 O(n^2)。是稳定的排序方法。 　　插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把 这个最后元素插入到此刻已是有序的第一部分里的正确位置中。

数组也可以像结构体一样初始化，未赋初值的元素也是用0来初始化，例如：

int count[4] = { 3, 2, };

实现：
#include
#include


void sort_insert(int a[], int N, int tmp)
{
    int i,j;
    for(i=0; i< N && a[i] < tmp ; i++);
    for( j = N; j > i ; j--)
        a[j] = a[j-1];
    a[i] = tmp;
}

void print_sort(int a[])
{
    int i;
    for(i=0;i<10;i++)
        printf("a[%d]=%d\n", i, a[i]);
}

int main(int argc,char **argv)
{
    int i;
    int a[10]={1,3,4,5,};

    printf("before insert:\n");
    print_sort(a);

    sort_insert(a,4,2);

    printf("after insert:\n");
    print_sort(a);

    return 0;
}

程序执行结果：
[root@localhost workspace]# !cc
cc sortInsert.c
[root@localhost workspace]#
[root@localhost workspace]# ./a.out
before insert:
a[0]=1  a[1]=3  a[2]=4  a[3]=5  a[4]=0  a[5]=0  a[6]=0  a[7]=0  a[8]=0  a[9]=0
after insert:
a[0]=1  a[1]=2  a[2]=3  a[3]=4  a[4]=5  a[5]=0  a[6]=0  a[7]=0  a[8]=0  a[9]=0
[root@localhost workspace]#