qsort的compare函数

qsort的compare函数

功能：使用快速排序例程进行排序
头文件：stdlib.h
用法：void qsort( void base, size_t num, size_t width, int (__cdecl *compare )(const void , const void *) );
qsort　参数：
1. base 待排序数组首地址
2. num 数组中待排序元素数量
3. width 各元素的占用空间大小
4. compare 指向函数的指针，用于确定排序的顺序

一维数组

int comp(const void* a,const void* b){
    return *(int*)a-*(int*)b;
}

二维数组

//a[1000][2]
qsort(a,1000,sizeof(int)*2,comp);
int comp(const void* a,const void* b) {
   return((int*)a)[0]-((int*)b)[0];
}

qsort函数base不同，compare函数不同

对二维数组排序，base是数组首地址。compare函数

//按照[0]从小到大排序，当[0]相等时按[1]从大到小排序
int comp(const void* a, const void* b) {
    if (((int*)a)[0] == ((int*)b)[0])
        return ((int*)b)[1] - ((int*)a)[1];
    else
        return ((int*)a)[0] - ((int*)b)[0];
}

对二维数组排序，base是二维数组指针的首地址。compare函数

//按照[0]从小到大排序，当[0]相等时按[1]从大到小排序
int comp(const void* a, const void* b) {
    int *aa = *(int**)a;
    int *bb = *(int**)b;

    if (aa[0] == bb[0]) {
        return bb[1] - aa[1];
    }
    return aa[0] - bb[0];
}

//按照[0]从小到大排序，当[0]相等时按[1]从大到小排序
int comp(const void* a, const void* b) {
    if ((*(int**)a)[0] == (*(int**)b)[0])
        return (*(int**)b)[1] - (*(int**)a)[1];
    else
        return (*(int**)a)[0] - (*(int**)b)[0];
}

第二种方法的效率更高。

字符串

int comp(const void* p1,const void* p2){
   return strcmp((char*)p2,(char*)p1);
}

结构体1

struct Node{
    double data;
    int other;
}s[100];
int comp(const void* p1,const void* p2){
    return (*(Node*)p2).data>(*（Node*）p1).data?1:-1;
}

结构体2

struct Node{
    int x;
    int y;
}s[100];
//按照x从小到大排序，当x相等时按y从大到小排序
int comp(const void*p1,const void*p2)
{
    struct Node*c=(Node*)p1;
    struct Node*d=(Node*)p2;
    if(c->x!=d->x)returnc->x-d->x;
    else return d->y-c->y;
}

结构体3

struct Node{
    int data;
    char str[100];
}s[100];
//按照结构体中字符串str的字典序排序
int comp(const void*p1,const void*p2){
    return strcmp((*(Node*)p1).str,(*(Node*)p2).str);
}
qsort(s,100,sizeof(s[0]),comp);

计算几何中求凸包的comp

//重点comp函数，把除了1点外的所有的点旋转角度排序
int comp(const void*p1,const void*p2){
    struct point*c=(point*)p1;
    struct point*d=(point*)p2;
    if(cacl(*c,*d,p[1])<0) return1;
    elseif(!cacl(*c,*d,p[1])&&dis(c->x,c->y,p[1].x,p[1].y)<dis(d->x,d->y,p[1].x,p[1].y))
//如果在一条直线上，则把远的放在前面
    return1;
    else return-1;
}

总结

void指针转换为类型指针，取指针指向的值比较。