C语言笔记：使用库函数qsort完成排序

落日映苍穹つ 2023-06-07 05:53 125阅读 0赞

### 文章目录 ###

*  简介
 *  对N个整数进行排序
 *  对N个浮点数进行排序
 *  对N个结构体元素进行排序
 *  对N个字符串进行排序
 *   *  二维字符数组方式
     *  指针数组的方式

# 简介 #

qsort 是stdlib.h的头文件中的万能排序函数，快速排序是目前公认的一种比较好的排序算法。因为他速度很快，所以系统也在库里实现这个算法，便于我们的使用。 这就是qsort函数(全称quicksort)。

函数原型：

void qsort(void *base,size_t nmem,size_t size,int (*cmp)(const void*,const void *) );

从左至右四个参数依次的解释：

*  base----指向待排序数组第一个元素的指针，排序之后的结果仍放在这个数组中
 *  nmem----由 base 指向的数组中元素的个数
 *  size----base指向的数组各元素的占用空间大小（单位为字节）
 *  cmp-----用来比较两个元素的函数，即函数指针（回调函数），用于确定排序的顺序（需要用户自定义一个比较函数）

应用qsort函数的难点在于正确编写cmp函数。下面具体讲解一下cmp函数：

典型的cmp函数定义原型为：

int cmp(const void *a,const void *b);

cmp参数指向一个比较两个元素的函数。注意两个形参必须是const void \*型，返回值必须是int型，同时在调用cmp函数（cmp实质为函数指针，这里称它所指向的函数也为cmp）时，传入的实参也必须转换成const void \*型。在cmp函数内部会将const void \*型转换成实际类型。该函数的函数体的编写决定快速排序是按升序还是降序

*  如果要按升序排序，则cmp返回值小于0（< 0），那么a所指向元素会被排在b所指向元素的前面；
 *  如果cmp返回值等于0（= 0），那么a所指向元素与b所指向元素的顺序不确定；
 *  如果要按降序排序，则cmp返回值大于0（> 0），那么a所指向元素会被排在b所指向元素的后面。

下面用例子来说明qsort函数对不同类型数据如何进行排序。函数体要对a,b进行强制类型转换后才能得到正确的返回值，类型不同处理方式稍有不同

# 对N个整数进行排序 #

#include <stdio.h>
    #include <stdlib.h>
    #define N 20//实例默认元素个数N不超过20 
    int cmp(const void *a,const void *b)
    { 
    // return (*(int *)a-*(int *)b);//升序排序时，此表达式应保证返回负整数 
    	return (*(int *)b-*(int *)a);//降序排序时，此表达式应保证返回正整数 
    } 
    int main(void)
    { 
    	int s[N];
    	int n;
    	printf("请输入元素个数：");
    	scanf("%d",&n);
    	printf("请一次性输入%d个整数（数与数之间用空格隔开）：\n",n);
    	for(int i=0;i<n;i++)
    	{ 
    		scanf("%d",&s[i]);
    	}
    	qsort(s,n,sizeof(s[0]),cmp);
    	printf("排序后的结果为：");
    	for(int i=0;i<n;i++)
    	{ 
    		printf("%d ",s[i]);
    	}
    	printf("\n");
    	return 0;
    }

输出：  
![在这里插入图片描述][20191013154348261.png]  
读者可以将cmp函数的第二个return注释掉，使用第一个return语句。则实现升序排序。

# 对N个浮点数进行排序 #

#include <stdio.h>
    #include <stdlib.h>
    #define N 20//实例默认元素个数N不超过20 
    int cmp(const void *a,const void *b)
    { 
    // return (*(double *)a>*(double *)b ? 1:-1);//升序排序时，此表达式应保证返回负整数 ,a所指向元素会被排在b所指向元素的前面
    	return (*(double *)b>*(double *)a ? 1:-1);//降序排序时，此表达式应保证返回正整数 ,a所指向元素会被排在b所指向元素的后面
    } 
    int main(void)
    { 
    	double s[N];
    	int n;
    	printf("请输入元素个数：");
    	scanf("%d",&n);
    	printf("请一次性输入%d个整数（数与数之间用空格隔开）：\n",n);
    	for(int i=0;i<n;i++)
    	{ 
    		scanf("%lf",&s[i]);
    	}
    	qsort(s,n,sizeof(s[0]),cmp);
    	printf("排序后的结果为：");
    	for(int i=0;i<n;i++)
    	{ 
    		printf("%lf ",s[i]);
    	}
    	printf("\n");
    	return 0;
    }

输出：  
![在这里插入图片描述][20191013155734662.png]  
要改变为升序，注释掉cmp函数的第二个return，使用第一个return 语句。

注意：在对浮点或者double型的一定要用三目运算符，因为要是使用像整型那样相减的话，如果是两个很接近的数则可能返回一个很小的小数（大于-1，小于1），而cmp的返回值是int型，因此会将这个小数返回0，系统认为是相等，失去了本来存在的大小关系。

# 对N个结构体元素进行排序 #

问题描述：  
以学生（学号，年龄）结构体为例，按年龄升序排序，如果年龄相同，则按学号升序排序

问题分析：  
学生类型（Student）定义成含有sno（学号）和age（年龄）成员的结构体类型，然后int cmp（const void \*a,const void \*b）函数体中，使用强化类型（Student \*）将a,b转换后，再根据年龄不同和相同写出对应的返回值。

#include <stdio.h>
    #include <stdlib.h>
    #define N 20//实例默认元素个数N不超过20 
    typedef struct Student
    { 
    	int sno;
    	int age;
    } Student;
    int cmp(const void *a,const void *b)
    { 
    	Student *aa=(Student *)a;//空类型指针强制转换为Student类型指针 
    	Student *bb=(Student *)b;//空类型指针强制转换为Student类型指针 
    	if((aa->age) != (bb->age))
    	{ 
    		return aa->age-bb->age;//a,b的年龄不同时，按年龄age升序 
    	}
    	else
    	{ 
    		return aa->sno-bb->sno;//a,b的年龄相同时，按学号sno升序 
    	}
    } 
    int main(void)
    { 
    	Student s[N];
    	int n;
    	printf("请输入元素个数：");
    	scanf("%d",&n);
    	printf("请输入%d个学生信息（学号 年龄）:\n",n);
    	for(int i=0;i<n;i++)
    	{ 
    		scanf("%d %d",&s[i].sno,&s[i].age);
    	}
    	qsort(s,n,sizeof(s[0]),cmp);
    	printf("排序后的结果为：");
    	for(int i=0;i<n;i++)
    	{ 
    		printf("\n%d %d",s[i].sno,s[i].age);
    	}
    	printf("\n");
    	return 0;
    }

输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]

# 对N个字符串进行排序 #

## 二维字符数组方式 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 20
    int cmp(const void *a,const void *b)//cmp函数体通过strcmp函数实现 
    { 
    	return strcmp((char *)a,(char *)b);//strcmp(s1,s2)函数，如果s1<s2，则返回负整数,s1指向字符串放到s2指向字符串前面 
    } 
    int main(void)
    { 
    	char s[N][21];
    	int n;
    	printf("请输入字符串个数：");
    	scanf("%d",&n);
    	printf("请输入%d个字符串：\n",n);
    	for(int i=0;i<n;i++)
    	{ 
    		scanf("%s", s[i]);//s[i]存放二维数组的每行首地址 
    	}
    	qsort(s,n,sizeof(s[0]),cmp);
    	printf("排序后的结果为：\n");
    	for(int i=0;i<n;i++)
    	{ 
    		printf("%s \n",s[i]);
    	}
    	printf("\n");
    	return 0;
    }

输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]  
首先比较三个字符串的第一个字符（以ASCII码大小比较），若第一个字符相同，接着比较第二个字符，得出如图排序结果

## 指针数组的方式 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 20
    int cmp(const void *a,const void *b)//cmp函数体通过strcmp函数实现 
    { 
    	return strcmp(*(const char **)a,*(const char **)b);//strcmp(s1,s2)函数，如果s1<s2，则返回负整数,s1指向字符串放到s2指向字符串前面 
    } 
    int main(void)
    { 
    	char *s[N];//每个串的长度最多20个字符 
    	int n;
    	printf("请输入字符串个数：");
    	scanf("%d",&n);
    	printf("请输入%d个字符串：\n",n);
    	for(int i=0;i<n;i++)
    	{ 
    		s[i]=(char *)malloc(21*sizeof(char));//每个元素占用21个字节空间
    		scanf("%s",s[i]); 
    	}
    	qsort(s,n,sizeof(s[0]),cmp);
    	printf("排序后的结果为：\n");
    	for(int i=0;i<n;i++)
    	{ 
    		printf("%s \n",s[i]);
    	}
    	printf("\n");
    	
    	for(int i=0;i<n;i++)
    	{ 
    		free(s[i]);
    	}
    	return 0;
    }

输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 2]  
此处的strcmp(\*(const char \*\*)a,*(const char \*\*)b)，是先强制转换成char \*\*，再用*减少一层间接寻址的操作。指针数组里的元素还是指针，指向真正的字符串，所以cmp函数里操作的字符串是需要双层指针（二级指针）才能访问的具体的字符串，故强制转换成char \*\*,在用strcmp（）函数时的的参数只需要指针数组的的元素指针即可，故用\*减少一层间接寻址操作。

[20191013154348261.png]: /images/20230601/0a51833151fa49c2b93821bc92e92f71.png
[20191013155734662.png]: /images/20230601/3a34d886a8c04f5ebc57a6ae4da7e557.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]: /images/20230601/bedefcbd49114477971c4ce705bae7cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]: /images/20230601/6ed959f79657461ab905c528b13bc31e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 2]: /images/20230601/57a918ae50f646e4a0a5a5beb736cc36.png