C语言快速排序–qsort函数 一.什么是qsort函数
qsort函数是C语言编译器函数库自带的快速排序函数。
其包含在#include<stdlib.h>头文件里面，所以在使用的时候需要加上该头文件。
二.qsort函数的时间复杂度
因为其本身还是快速排序，所以时间复杂度仍然是O（nlogn）
（在洛谷做题的时候，感觉它还是比传统的快排要更快，传统的快排最后三个会TLE，但是使用qsort函数就不会）
三.具体讲解 1.描述 sqort函数对数组进行排序 2.声明
下面是 qsort() 函数的声明。
void qsort(void *base, size_t nitems, size_t size, int (*compare)(const void *, const void*)) 3.参数
base – 指向要排序的数组的第一个元素的指针。
nitems – 由 base 指向的数组中元素的个数。
size – 数组中每个元素的大小，以字节为单位。
compare – 用来比较两个元素的函数。
4.compare
自己定义一个compare函数，用来比较a和b的大小
int compare(const void *a,const void *b){return *(int*)a-*(int*)b;} （int *）a表示将a地址强制类型转换成整形地址类型*(int*)a 就是得到目标地址的值 //对int型数据进行升序排序 int compare1(const void *a,const void *b){return *(int*)a-*(int*)b;}//对int型数据进行降序排序 //依次类推，所有的都可以这样进行降序排序int compare2(const void *a,const void *b){return *(int*)b-*(int*)a;}//对double型数据进行升序排序 int compare3(const void *a,const void *b){return *(double*)a-*(double*)b;}//对char型数据进行升序排序 int compare4(const void *a,const void *b){return *(char*)a-*(char*)b;}//字符串长度排序 int cmppare5(const void *a, const void *b){ return strlen((char *)a) - strlen((char*)b);}//结构体排序int compare6(const void *a,const void *b){return ((*(node*)a).x-(*(node*)b).x)==0?(*(node*)a).y-(*(node*)b).y:(*(node*)a).x-(*(node*)b).x;}
升序排序：*(int*)a-*(int*)b;
降序排序（a与b位置互换）：*(int*)b-*(int*)a;
五.五种常用的qsort函数代码
1.int型
2.double型
3.char型
4.字符串型
5.结构体型
//1.对整数排序#include<stdio.h>#include<stdlib.h>#define MAXN 100010int n,a[MAXN];//升序排序int compare1(const void *a,const void *b){return *(int*)a-*(int*)b;}//降序排序int compare2(const void *a,const void *b){return *(int*)b-*(int*)a;}int main(){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);qsort(a,n,sizeof(int),compare1);//qsort(a,n,sizeof(int),compare2);for(int i=0;i<n;i++)printf("%d ",a[i]);return 0;} //2.对double型排序#include<stdio.h>#include<stdlib.h>#define MAXN 100010int n;double a[MAXN];int compare1(const void *a,const void *b){return *(double*)a-*(double*)b;}int compare2(const void *a,const void *b){return *(double*)b-*(double*)a;}int main(){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lf",&a[i]);qsort(a,n,sizeof(double),compare1);for(int i=0;i<n;i++)printf("%lf ",a[i]);return 0;} //3.对char型排序#include<stdio.h>#include<stdlib.h>#define MAXN 100010int n;char a[MAXN];int compare1(const void *a,const void *b){return *(char*)a-*(char*)b;}int compare2(const void *a,const void *b){return *(char*)b-*(char*)a;}int main(){scanf("%d",&n);for(int i=0;i<n;i++)scanf(" %c",&a[i]);qsort(a,n,sizeof(char),compare1);for(int i=0;i<n;i++)printf("%c ",a[i]);return 0;} //4.1对字符串排序//按照长度大小排序#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXN 100010int n;char a[MAXN][MAXN];int compare1(const void *a, const void *b){return strlen((char *)a) - strlen((char *)b);} int compare2(const void *a, const void *b){return strlen((char *)b) - strlen((char *)a);}int main(){scanf("%d",&n);getchar();//吃掉换行符;for(int i=0;i<n;i++)gets(a[i]);qsort(a,n,sizeof(char)*MAXN,compare1);for(int i=0;i<n;i++)printf("%sn",a[i]);return 0;} //4.2对字符串排序//按照首字母大小排序#include<stdio.h>#include<stdlib.h>#define MAXN 100010int n;char a[MAXN][MAXN];int compare1(const void *a,const void *b){return *(char*)a-*(char*)b;}int compare2(const void *a,const void *b){return *(char*)b-*(char*)a;}int main(){scanf("%d",&n);getchar();//吃掉换行符;for(int i=0;i<n;i++)gets(a[i]);qsort(a,n,sizeof(char)*MAXN,compare1);for(int i=0;i<n;i++)printf("%sn",a[i]);return 0;} //5.对结构体排序#include<stdio.h>#include<stdlib.h>#define MAXN 100010int n;struct node{int x;char y;}name[MAXN];//对结构体中的x进行排序int compare1(const void *a,const void *b){return (*(node*)a).x-(*(node*)b).x;}//对结构体中的y进行排序int compare2(const void *a,const void *b){return (*(node*)a).y-(*(node*)b).y;}//利用三元运算符,将排序顺序改为：//先按照结构体中的x进行排序，假如x相等的情况下，就按照y//的值进行排序;int compare3(const void *a,const void *b){return ((*(node*)a).x-(*(node*)b).x)==0?(*(node*)a).y-(*(node*)b).y:(*(node*)a).x-(*(node*)b).x;}int main(){scanf("%d",&n);getchar();//吃掉换行符;for(int i=0;i<n;i++)scanf("%d %c",&name[i].x,&name[i].y);qsort(name,n,sizeof(node),compare1);//qsort(name,n,sizeof(node),compare2);//qsort(name,n,sizeof(node),compare3);for(int i=0;i<n;i++)printf("%d %cn",name[i].x,name[i].y);return 0;}