算法竞赛中，排序是非常重要的内容。无论是可以用来算逆序对的归并排序，还是广泛运用在贪心算法里的快速排序，对它们的熟练掌握，都会让程序拥有更高的效率。在这篇文章里，我想说说自己对qsort的一点思考。
1. 语法--以单关键字排序为例
C语言的stdlib.h中有qsort的库函数，可以直接使用，非常方便。
void qsort(void * base, size_t num, size_t size, int (*comparator)(const void *, const void *));
如何使用它：
#include<stdlib.h>
int a[1001];
int cmp( const void * x, const void * y){
if (*(int *)x < *(int *)y) return -1; //格式可以记为 *(类型名 *) 变量名
else return 1;
}
int main(void){
int i,n;
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
qsort(a+1, n, sizeof(a), cmp); //数组是从a[1]开始存的
for (int i=1; i<=n; i++) cout<<a[i]<<endl;
return 0;
}
总结一下，qsort的语法是，
qsort(需要排序的数组的起始内存地址位置，元素个数，单个元素大小，比较函数)；
比较函数cmp的特点是，如果返回值为负数，就不做修改；如果返回值为正数，就要交换两数位置。所以qosrt本质上是一个基于比较与交换的算法，其根据比较函数的返回值来决定是否要对元素进行交换。
同时也想提一下比较函数中的 " const void * "，在大名鼎鼎的《算法竞赛入门经典》（以后我会根据大家的习惯把它称为‘紫书’）一书中，刘汝佳老师称它为“指向函数的‘万能’指针”：“它可以通过强制类型转化变成任意类型的指针”。在函数中，"*(int *) x" 会将“void *”类型转化成“int *”类型，再用“*” 运算符提取出对应的元素。
（碎碎念：用markdown打星号好不方便……一不小心就变成斜体字了2333）
2. 双关键字排序
双关键字排序一般用qsort+stuct来实现。当我们有两个变量需要同时进行比较时，双关键字排序会起到非常重要的作用。
还是想啰嗦一下，在我们遇到需要在移动变量1的同时移动变量2这种情况时，结构体是更为方便的选择。因为当a[1].x在比较之后被确定需要swap之时，a[1].y也会随着结构体的变动而变动。
一言不合就上代码：
struct aa{ int x,y; } a[N];
int cmp(const void * x, const void * y){
aa p1 = *(aa *) x; aa p2 = *(aa *) y;
if (p1.x < p2.x) return -1;
if (p1.x > p2.x) return 1;
if (p1.y < p2.y) return -1;
return 1;
}
qsort(a+1, n, sizeof(aa), cmp);
3. 多关键字排序
多关键字排序本质上和双关键字排序完全相同。这里附上三关键字排序的代码。理解之后，无论有多少个关键字，都会很容易写出来。
struct aa{ int x,y,z; } a[N];
int cmp(const void * x, const void * y){
aa p1 = * (aa *) x; aa p2 = * (aa *) y;
if (p1.x < p2.x) return -1;
if (p1.x > p2.x) return 1;
if (p1.y < p2.y) return -1;
if (p1.y > p2.y) return 1;
if (p1.z < p2.z) return -1;
return 1;
}
4. 例题
最后想放例题以详细说明qsort在实战中的使用。感兴趣的同学，不妨先去试试看，再来看我的代码。当然，如果你们有更好的方法或者更优美的代码，也欢迎交流~：）
OnlineJudge: UVa
Problem #: 1339
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
char a[105], b[105];
int cmp(const void *x, const void *y){
if (*(int *)x < *(int *)y) return -1;
else return 1;
}
int main(void){
//freopen("uva1339.txt","r",stdin);
while(scanf("%s%s", a, b) != EOF){
int n = strlen(a);
int cnt1[26]; int cnt2[26];
memset(cnt1,0,sizeof(cnt1)); memset(cnt2,0,sizeof(cnt2));
for(int i=0;i<n;i++){
cnt1[a[i]-'A']++;
cnt2[b[i]-'A']++;
}
qsort(cnt1,26,sizeof(int),cmp);
qsort(cnt2,26,sizeof(int),cmp);
bool flag=true;
for(int i=0;i<26;i++){
if(cnt1[i]!=cnt2[i]){
flag=false;
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
OnlineJudge: UVa
Problem #: 1587
#include<iostream>
#include<stdlib.h>
using namespace std;
struct aa{
int x,y;
}a[7];
int cmp(const void *x, const void *y){
aa p1=*(aa*)x; aa p2=*(aa*)y;
if(p1.x<p2.x)return -1;
if(p1.x>p2.x)return 1;
if(p1.y<p2.y)return -1;
return 1;
}
int main(void){
//freopen("uva1587.txt","r",stdin);
while(~scanf("%d", &a[0].x)){
scanf("%d",&a[0].y);
if(a[0].x>a[0].y) swap(a[0].x,a[0].y);
for(int i=1;i<6;i++){
scanf("%d%d",&a[i].x,&a[i].y);
if(a[i].x>a[i].y) swap(a[i].x,a[i].y);
}
qsort(a,6,sizeof(aa),cmp);
int error = 0;
for(int i=0; i<3; i++)
{
if(a[i*2].x!=a[i*2+1].x || a[i*2].y!=a[i*2+1].y)
{
error = 1;
break;
}
}
if(!error && a[0].x==a[2].x && a[0].y==a[4].x && a[2].y==a[4].y)
printf("POSSIBLE\n");
else
printf("IMPOSSIBLE\n");
}
return 0;
}
特别鸣谢：
我的第一位也是迄今为止唯一的算法老师：弟弟 （NOIP与ACM大神一枚）
参考资料：
- 《算法竞赛入门经典》刘汝佳
