快排函数qsort（C语言）

系统管理员 2022-04-23 21:12 213阅读 0赞

**头文件**

<stdio.h>

**函数原型：**

void qsort(
        void *base,		 //需要排序的数组的首地址（即数组名）
        size_t nmemb,		//数组中元素的个数
        size_t size,			//数组中每个元素的大小
        int (*cmp) (const void *, const void *)		//指向比较函数的函数指针，决定了排序的顺序
        );

注意：

如果两个元素的值是相同的，那么它们的前后顺序是不确定的。也就是说qsort()是一个不稳定的排序算法。

**cmp参数：**

int cmp(const void *p1, const void *p2);

注意：  
1、两个形参必须是const void \*型  
2、在cmp函数内部会将const void \*型转换成实际类型

原则：  
如果cmp返回值小于0（< 0），那么p1所指向元素会被排在p2所指向元素的前面  
如果cmp返回值等于0（= 0），那么p1所指向元素与p2所指向元素的顺序不确定  
如果cmp返回值大于0（> 0），那么p1所指向元素会被排在p2所指向元素的后面

**情景一：**

int类型

（1）从小到大排列

int cmp(const void *c,const void *d)
    { 
        return *(int *)c-*(int *)d;
    }

（2）从大到小排列

int cmp(const void *c,const void *d)
    { 
        return *(int *)d-*(int *)c;
    }

**情景二：**

double类型

（1）从小到大

int inc (const void * a, const void * b)
    { 
    return *(double *)a > *(double *)b ? 1 : -1;
    }

（2）从大到小

int inc (const void * a, const void * b)
    { 
    return *(double *)a > *(double *)b ? -1 : 1;
    }

**情景三：**

字符排序

int inc(const void *a,const void *b)
    { 
      return *(char *)a - *(char *)b;	//从小到大
    }

**情景四：**

字符串排序

char a[m][n] = {  { "...."}, { "....."}, .....};
    qsort(a, m, sizeof(a[0]), inc);

（1）根据字符串首字母排序

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

（2）根据字符串长度排序

int inc(const void *a, const void *b)  
    {   
    return strlen((char * )a) > strlen((char * )b) ? 1 : -1;  
    }

（3）按字典排序字符串

int inc(const void *a, const void *b)
    { 
    return (strcmp((char *)a, (char *)b));
    }

**情景五：**

结构体类型

struct node
    { 
      double one;
      int two;
    } s[100];

（1）.一级排序  
根据double型的one的大小排序结构体

int inc( const void *a ,const void *b)
    { 
    return ( * (node * )a).one > ( * (node * )b).one ? 1 : -1;
    }

（2）二级排序  
先根据double型的one的大小排序，若两值相等，在根据int型two的大小排序

int inc( const void *a , const void *b )
    { 
    if((* (node * )a).one != ( * (node * )b).one)
    return ( * (node * )a).one > ( * (node * )b).one ? 1 : -1;
    else return (* (node * )a).two -( * (node * )b).two;
    }