插值排序

//插值排序的使用环境：小规模数据需要排序，并且初始数据几乎是有序
//基于指针的插入排序
void SortPointers(void **ar, int n, int(*cmp)(const void *, const void *))
{
    int j = 0;
    int i = 0;

    for(j=1; j    {
        i = j - 1;
        void *pValue = ar[j];
        while(i>=0 && cmp(ar[i], ar[j]) > 0)
        {
            ar[i+1] = ar[i];
            i--;
        }
        ar[i+1] = pValue;
    }
}

//对于基于值的排序，使用内存块的移动函数，可以使算法更加高效
//基于值的插入排序
void SortValues(void *base, int n, int s, int(*cmp)(const void *, const void *))
{
    int j=0;
    int i=0;
    
    for(j=1; j    {
        void *pValue = malloc(s);
        i = j - 1;

        while(i>=0 && cmp(base+i*s, base+j*s) > 0)
        {
            i--;
        }

        if(++i == j)
        {
            continue;
        }

        memmove(pValue, base+j*s, s);
        memmove(base+(i+1)*s, base+i*s, s*(j-i));
        memmove(base+i*s, pValue, s);
        free(pValue);
        pValue = NULL;
    }
}

    插入排序在随机数据面前太过于保守，如果所有n个元素都是不同的，而且数组是随机（数据的所有排列出现概率相等），那么每一个元素离其最终的位置平均距离是n/3.所以在平均情况和最坏情况下，n个元素中的每个元素会被移动一个线性距离，插入排序是二次方的运行时间，O(n^2)。

    插入排序对于基于值的数据效率很低，因为很多内存需要移位，以给新的值腾出位置。使用内存块移动的插入排序的性能是原生插入排序性能的常数倍（大约1/7）,插入排序的问题是它是一种保守算法（本地移位排序），这类算法每个元素一次移动一个位置。
参考：《算法技术手册》