Insertionsort

算法作用：将一个无序的数组a 按照非降序排序！

算法思想：将a[1] 和 a[0]比较大小，如果比a[0]小，把a[0] 后移一位，插入a[1],然后将a[2]依次和a[1] a[0]比较大小，当比a[2] 小的时候一直后移，然后插入a[2]。 依次循环知道所有元素排序完成！

#include<stdio.h>
#include<malloc.h>
void insertionsort(int *a, int N){
     int i = 1;
     int j,x;
     while (i<N){
        int j = i;
        x = a[i];
        while ((j>0)&&(a[j-1]>x)){
               a[j] = a[j-1];
               j = j -1;
            }
        a[j] = x;
        i = i+1;
     }
}
int main()
{
    int N,i;
    int *a;
    printf("Please input the number of the array:");
    scanf("%d", &N);
    a = (int* )malloc(N*sizeof(int));
    for(i=0; i<N; i++)
        scanf("%d",&a[i]);
    insertionsort(a, N);
    for(i=0; i<N; i++)
        printf("%3d",a[i]);
}