2.1 插入排序:
接口定义：
int insert_sort(void* data, int size, int esize,
int (*compare)(const void* key1, const void* key2));
返回值：成功 0；失败 -1。
算法描述：
每次从待排序数据集中取出第一个元素，将其插入到有序数据集中，两个数据集共用一块存储空间。两个数据集都存放在data中，data包含size个无序元素，每个元素的大小为esize，函数指针compare指向一个比较元素大小的用户自定义函数。最初，data指向size个无序元素，但是在执行insert_sort时，data所指的空间逐渐被有序元素所取代。
算法分析：
插入排序使用嵌套循环来实现，外循环用于控制循环次数，同时也代表了当前待排序的元素；内循环用于找出当前元素的正确插入位置。插入排序从第二个元素开始插入，因此，外循环需要执行n-1次。在寻找插入位置时，考虑最坏的情况（即逆序数据集中：每次插入的元素刚好是有序数据集中的最小值），则在第num次循环中，需要num次比较操作，如此，整个嵌套循环的执行时间：T(n) = [1 + 2 + 3 + ... + (n - 1)] / 2 = n(n - 1) / 2 ---> O(n2)。对于正序数据集而言，其时间复杂度为O(n)。插入算法不需要额外的存储空间。
算法实现：
/*
insert_sort():
返回值：成功0；失败 -1
*/
int insert_sort(void* data, int size, int esize,
int (*compare)(const void* key1, const void* key2))
{
char* pd = (char*)data;
void* pcur;
int num, ipos; /* 分配一块元素大小的内存 */
if((pcur = (char*)malloc(esize)) == NULL)
return -; /* 在有序数据集中循环插入待排元素 */
for(num = ; num < size; num++)
{
/* 将待排元素复制到pcur中，第一个元素默认有序，从第二个元素开始 */
memcpy(pcur, &pd[num * esize], esize); /* 寻找插入位置ipos */
ipos = num - ;
while((ipos >=) && (compare(&pd[ipos * esize], pcur) > ))
{
/* 如果*pcur < pd[ipos]，则pd[ipos]后移 */
memcpy(&pd[(ipos + ) * esize], &pd[ipos * esize], esize);
ipos--;
}
memcpy(&pd[(ipos + ) * esize], pcur, esize); }
/* 释放内存 */
free(pcur); return ;
2.2 快速排序：
接口定义：
int partition(void* data, int esize, int lpos, int rpos,
int (*compare)(const void* key1, const void* key2));
返回值：成功 ppos；失败 -1
int quick_sort(void* data, int size, int esize,
int lpos, int rpos, int (*compare)(const void* key1, const void* key2));
返回值：成功 0；失败 -1
算法描述：
快速排序利用分治法的思想，首先设定一个分割值pval将数据集分为左右两个分区，然后分别对左右两个分区使用快速排序，如此递归直至区间中只有一个元素为止。数据集data包含size个无序元素，每个元素的大小为esize，函数指针compare指向一个比较元素大小的用户自定义函数。lpos和rpos分别为与当前分割值pval进行比较的位置。首次调用quick_sort()时，lpos设为0，rpos设为size – 1，相当于对全部元素进行排序（也可以自己设定感兴趣区间进行排序）。以partition()函数返回的ppos作为分割界限将数据集分为左右两个区间。分别对两个分区递归地进行快排，直至传入quick_sort()的分区只包含一个元素为止，此时排序完成。
算法分析：
影响快速排序算法性能的关键是分割值的选取，也就是partition()函数如何分割数据集。分割值一般不能太极端，这样会使得大部分数据被分到一个分区中，此时，快排的性能非常差，为O(n2)。一个比较好的方法是在区间中随机选择三个元素，然后选择三个元素中的中间值，就是通常的中位数法，实验表明该方法可以使得快排接*均性能O(nlgn)。另外快速排序不需要额外的存储空间。
算法实现：
/*
partition():
return: success ppos; fail -1
*/
int partition(void* data, int esize, int lpos, int rpos,
int (*compare)(const void* key1, const void* key2))
{
char* pd = (char*)data;
void* pval; /* partition value */
void* ptemp;
int r[]; /* 为partition value和swapping分配空间 */
if((pval = malloc(esize)) == NULL)
return -;
if((ptemp = malloc(esize)) == NULL)
{
free(pval);
return -;
} /* 计算partition value */
r[] = (rand() % (rpos - lpos + )) + lpos;
r[] = (rand() % (rpos - lpos + )) + lpos;
r[] = (rand() % (rpos - lpos + )) + lpos;
insert_sort(r, , sizeof(int), compare_int);
memcpy(pval, &pd[r[] * esize], esize); /* 根据pval进行partition */
lpos--;
rpos++;
while()
{
/* 如果pd[rpos * esize] > *pval, 将rpos左移 */
do{
rpos--;
}while(compare(&pd[rpos * esize], pval) > ); /* 如果pd[lpos * esize] < *pval, 将lpos右移 */
do{
lpos++;
}while(compare(&pd[lpos * esize], pval) < ); if(lpos >= rpos)
break; /* 停止partition */
else
{
/* 交换lpos和rpos处的元素 */
memcpy(ptemp, &pd[lpos * esize], esize);
memcpy(&pd[lpos * esize], &pd[rpos * esize], esize);
memcpy(&pd[rpos * esize], ptemp, esize);
}
} /* 释放空间 */
free(ptemp);
free(pval); return rpos;
}
/*
quick_sort():
return: success 0;
*/
int quick_sort(void* data, int size, int esize,
int lpos, int rpos, int (*compare)(const void* key1, const void* key2))
{ int ppos;
if(lpos < rpos)
{
if((ppos = partition(data, esize, lpos, rpos, compare)) < )
return -; /* 递归地对左分区进行排序 */
if(quick_sort(data, size, esize, lpos, ppos, compare) < )
return -; /* 递归地对右分区进行排序 */
if(quick_sort(data, size, esize, ppos + , rpos, compare) < )
return -;
} return ;
}