qsort的比较函数
缘起
之前实习时，同事遇到一个看起来诡异的bug，现象是用标准库的qsort函数得不到正确结果。
而同样的代码在别人电脑上却没有问题。一度怀疑是不是glibc的锅。
代码大概是这样的：
#include <stdlib.h>
int cmp(const void *a, const void *b)
{
return *((int *)a) > *((int *)b);
}
int main()
{
int array[] = {4, 2, 5, 2, 4, 67, 3, 5, 2, 4};
qsort(array, sizeof(array)/sizeof(int), sizeof(int), cmp);
return 0;
}
平时C写得多的同学估计一眼就看出来问题所在了。cmp函数中，a和b之间不应该用大于号比较，因为qsort函数是通过cmp函数返回正/负/零来判断元素间大小关系的。而由于C语言的隐式类型转换，上述cmp函数只会返回0或1。
不难总结，在a >= b时，这个错误的cmp函数会返回正确的结果。
同时反向思考，cmp返回1时，可以保证a > b，cmp返回0时，a可能小于b，也可能等于b。
综上，cmp > 0是a > b的充要条件。cmp = 0是a = b的必要不充分条件，同时也是a <= b的充要条件。
所以排序得到错误结果也在意料之中了。
但是这段错误的代码为何在其他人的电脑上却可以得到正确结果呢？
这就取决于不同库对qsort的实现了。不同标准库内部实现是可以不同的，虽然能保证它们在正确情况下有相同表现，但是错误情况下，返回什么结果就都是未定义的了。
然而有意思的是，为什么有些库可以得到正确结果？是特定数据下的一种巧合么？
正确输入得到错误输出，需要问问为什么。错误输入却得到正确输出，更要问问为什么！
谜底
首先解释一下同事为何会犯这么常识性的错误。
他之前一直写的是C++，而C++中std::sort函数传入的comparator返回的是bool型，因此在C++中这么写是没有问题的，便把C++中的习惯带到了C语言中。
STL中的sort只需要返回bool值的comparator就可以进行排序，所以qsort要求返回正/负/零三种值显然是存在信息冗余的。毕竟快速排序法只需要对数组进行二分，而不是三分。
因此，有些库采取了类似std::sort的实现方式（std::sort默认使用std::less进行比较），只考察a是否大于b，而如前文所说，此时cmp > 0是a > b的充要条件，即此错误的cmp函数和正确的comparator函数行为一致，所以可以得到正确的结果。
同时，前面说了，并不保证所有库都是这么实现，并且qsort函数一般不止使用快速排序这一种算法，在递归深层，可能还会使用插入/选择排序法。因此能得到正确的结果真是非常巧了（如果库作者当初就料想到有人会传入这种错误的comparator而刻意这么实现，我一点都不佩服他，因为正确的做法应该是对于错误的输入就及时报错）。
结语
可见，C语言的隐式类型转换以及未定义行为真是“可怕”，以及一些存在历史遗留问题的库函数（譬如你知道getchar的返回值是什么？），都是滋生bug的温床。但事实上这些bug也挺有意思，多关注关注这些问题，是通往“伪专家”的捷径。
最后留道思考题：
编写一个qsort实现，在传入上述错误的cmp函数的情况下也能排序得到正确结果。
更进一步，如果不是return *((int *)a) > *((int *)b);而是return *((int *)a) >= *((int *)b);，刚才的代码依然work么？