插入排序：

类似洗牌，将从1~N的数字分别插入到合适的位置，当然对于数组来说，需要做相应的移动。基础的方法是依次挪动，较为快捷的方法是memmove。

需要说明的是，按照Linux的man手册，memmove是支持内存overlap的，即可以部分重叠，函数内部会处理好其他的事情，因此类似书上的先移动到buffer，再从buffer移动到另一个位置是没必要的！

#include <stdio.h>
#include <string.h>

typedef int TYPE;

//Compare function
int cmp(TYPE a, TYPE b)
{
    return a - b;
}

//Inser Sort & Move one by one
void insert_sort_1(TYPE* arr,int n,int (*cmp)(TYPE,TYPE))
{
    int pos;
    for(pos = 0; pos < n; pos ++ )
    {
        TYPE value = arr[pos];
        int i;
        for(i = pos -1; i>=0; i-- )
        {
            if(cmp(arr[i],value)<0)
            {
                break;
            }
            else
            {
                arr[i+1] = arr[i];
            }
        }
        arr[i+1] = value;
    }
}

//Insert sort & move by memmove
void insert_sort_2(TYPE* arr,int n,int (*cmp)(TYPE,TYPE))
{
    size_t pos;
    for( pos = 1 ; pos < n ; pos++ )
    {
        TYPE value = arr[pos];
        int i = pos - 1;
        int len;
        while( i >= 0 && cmp( value , arr[i] ) < 0 ) { i--; }
        len = sizeof(TYPE) * (pos - i - 1);
        memmove( &(arr[i+2])  , &(arr[i+1])  , len  );
        arr[i+1] = value;
    }
}

int main()
{
    TYPE arr[8] = {1,3,2,5,8,12,0,3};
    const int size = sizeof(arr)/sizeof(TYPE);
    //Test for sort algorightm
    //insert_sort_1(arr,size,cmp);
    insert_sort_2(arr,size,cmp);
    int i;
    for(i=0;i<size;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
}