运用指针知识深入浅出探索qsort函数的用法
刘树明
(深圳市第二实验学校，广东 深圳 518021)
对数组的排序操作可以说在我们日常编程中是十分频繁的工作，其中快速排序算法就是我们经常采用的，它的好处是能够利用已经执行比较操作获得的结果来确定那些没必要比较就能确定大小关系的数组元素的排序位置(在快速排序中，如果已经通过比较知道a>b,b>c，就不会再执行a与c的比较了，因为a肯定会大于c)，从而减少时间复杂度。快速排序算法虽然性能优越，但是如果每次都自己手工编写排序算法，仍然需要熟记算法，而且一不留神就会出一些差错，很是麻烦。幸好C/C++语言（本文以下行文中，C/C++语言用“C类语言”来表达）有一个标准库函数qsort可以使用，这样一来我们就可以站在前人的肩膀上，不必要次次都重复低级的劳动，而且可以确保算法绝对是正确的，真是省时、省力、还省心！
由于qsort提供了很好的参数接口，掌握它的用法也并不难。但是如果不能深入研究并掌握指针知识，不对它做进一步的探索的话，多数人都只能是知其然却并不知其所以然，停留在貌似掌握、只能拿它来做一些初级的利用的程度上。拿着火箭炮当梭镖使用，不能发挥它的全部威力，碰到一些复杂场合，依然是无计可施，最后只能是另寻它法解决。在本文中，我们就各种可能出现的复杂场合下的qsort各种用法做出一番探索，并给出在每种情况下调用qsort解决排序问题的实例介绍，帮助大家彻底解决排序问题。
qsort函数构思精巧，灵活运用了地址和指针，在没有使用模板的情况下，能支持任何数据类型的快速排序，基于这一点来说，它不但是一个非常优秀的编程精典范例，也是一个能让我们学习和掌握指针用法不可多得的学习素材(qsort函数的完整定义在qsort.c源文件中，有的C类语言平台只提供已经静态编译好的函数库，并没有提供这个源文件，但也有部分的C类语言平台有提供这个源文件,这是一个400行多一点的源程序文件，限于本文篇幅，不在此处作介绍，但文件里面布满了注释，相信阅读起来不是很困难)。指针作为C类
语言的重要知识点，向来难以被学习者掌握，想要领会指针精髓，通常都需要在指针的应用方面做大量的实践。而在C类语言教材中相关的示例素材都比较少，函数指针方面的素材更是难找。而在qsort函数的编写和应用中却几乎涵盖了指针、地址、函数指针、数组指针、指针数组、指针的指针等等与指针有关的知识的运用。 在同一个函数中覆盖了几乎所有关于指针的用法，并且在各种用法灵活程度上能达到淋漓尽致的程度，可以说是十分的不容易了，就象是对对联中的千古绝对，除此下联，断难寻其它(不过在C类语言还有一个我们平时使用不多的函数也有这个特点，它就是二分查找函数bsearch，有兴趣的同学可以自己去研究研究)。我们通过对qsort的钻研和使用方面的探索，可以加深对指针相关概念的理解、掌握和融会贯通。
qsort的原型是在stdlib.h和search.h头文件中都有声明的，声明原型是
_CRTIMP void __cdecl qsort(void*, size_t, size_t,int (*)(const void*, const void*));
其中有两个我们读不懂的单词不需要理会，它们不会影响到我们的调用，_CRTIMP是用来告诉编译器是使用动态链接还是静态链接，__cdecl是告诉编译器调用函数时，参数的入栈退栈方式。我们将它简化后的函数原型是：
void qsort(void*base, size_t nelem, size_t width,int (*)(const void*,const void*));
从函数原型看出它是一个无返回值的函数，它有四个参数，其中第一个base是无类型指针，它可以接收任何类型的地址(注：无类型指针可以接收任何其它类型的地址，但是却不能将它直接赋给其它非无类型指针，不过可以将它强制转换成其它类型的指针后再赋给其它指针。这个有点类似血型中的AB型血，他可以接受任何人的献血，但不可以献血给其他
1
血型不同的人，不同之处是我们在献血的时候不能强制将血型转化一下再献给与自己血型不同的人)；第二个参数和第三个参数都是size_t类型即无符号整型（size_t被定义成了unsigned int），第四个参数是一个函数指针（它将来要指向比较函数，比较函数负责比较待排序数组的两个元素，以确定它们是否应当交换顺序），这个指针指向的函数必须是返回
值为整型，而且它有两个参数，这两个参数可以是任何的类型。
作为C类语言提供的标准库函数，qsort函数对头文件的依赖程度十分低，我们根本不用担心它是否能用的问题。首先它直接声明在stdlib.h中，这个头文件在绝大多数C语言编程中都必须要包含进来；而在C++语言中更是不用担心，stdlib.h被直接或者间接包含在这些头中：cstdlib,iostream,fstream,istream,ostream,string, memory... 等等，几乎所有常用的文件头都直接或者间接地包含了stdlib.h，我们在绝大多数的场合调用qsort都不需要再作特别的头文件包含。
使用qsort函数前的需要做的一项重要工作是如何定义比较函数。比较函数确定比较数组中的两个元素的方式，以确定是否需要交换它们的值。可以说排序是否正确，是以升序或者降序的方式排序，一切都只由比较函数决定。还有一个很耐人寻味的事情，就是尽管比较函数是我们自己预先定义好，但是调用它的却不是我们自己，我们能做的只是将它的地址（即函数名）以实际参数的方式传递给qsort，调用这个函数的是我们那位尊敬的qsort函数先生!它在做出是否交换两个元素的决定之前，将这两个元素的指针传递给我们的这个compare函数，并调用它，然后再依据它的返回值决定是否要交换，如果返回的是负数则不交换否则交换。
下面我们在各种场合下对qsort的调用方法做一些示例说明。 一、 普通数据类型调用qsort进行快速排序。
假设数组是：int a[MAXNUM]; 先定义一个compare函数：
int compare(const void *a,const void *b) { }
int *pa,*pb;
pa=(int *)a;pb=(int *)b;//先强制转换成整型指针pa,pb
return *pa-*pb;//按升序排列，即第一个数小于第二个数时返回负整数，不交换位置， //若要降序排列，则改为return *pb-*pa;即第一个数小于第二个数时返回正数，交换位置。
调用方法：qsort(a,sizeof(a)/sizeof(a[0]),sizeof(a[0]),compare);
我们可以看到，第一个参数接收的是数组的起始地址；第二个参数是告诉qsort这个数组有多少个元素；第三个参数是告诉qsort数组的每个元素的大小是多大，第四个参数不需要再说明了。整个调用除了比较函数需要我们另外定义以便告诉qsort我们的两个变量该如何比较大小外，其它的地方都简洁明了，可以说是远比手写快排要省力气得多。
这里有个小问题可能有人会感到纳闷，为何每个元素有多大也必须要告诉qsort呢？我们知道指针变量保存的就是变量的地址，不过这个还不能充分清楚地刻划出指针的含义，指针的类型其实对它来说也是至关重要的，类型决定了指针的管辖范围。我们把内存理解成一排长长的被均匀分割的单元格，其中每个格就代表一个字节，每一格也有一个唯一的编号，当然这些编号是连续的。变量就在内存中“居住”，每个变量占据着若干格，其中每一格都各有一个地址，指针要指向它的话，显然不可能将连续的这几个编号都保存在指针变量中，它实际上只保存了第一格的编号，那我们该如何知道后面的多少格都归它管辖呢？答案是由这个变量的类型来决定，变量的类型能决定这个变量占据多少格，那么自从指针变量中保存
2
的地址编号开始，后面连续的几格都归属这个变量了。现在我们这里的第一个参数传递过去的那个地址a，被qsort接收到后，变成了无类型的指针，类型丢失了，指针就失去了判定管辖范围的依据了，没有管辖依据，读取变量的操作就无法进行，所以我们后面必须另外来一个补充告知。
事实上如果我们阅读了qsort.c源文件后，就会发现，原来qsort之所以能处理任何数据类型的奥妙之处，在于它不管对方传给它的数据是何种类型，通通都转化成字符型(char)，然后从起始地点开始，按快速排序的思路将相关的数组元素的起始地址传给compare函数去判定是否交换位置，如果需要交位置，它就根据每个元素的起始地址和它占据了多少个字节，一个字节一个字节地搬过去(而不是采用我们平时编程中直接赋值的方式)，以完成交换过程。交换过程貌似相当的低效吧？事实上的确如此，有经验的人经常发现调用系统的的快排会比手写的快排要稍慢一点，原因就在这里。比如两个整型的变量，手写交换内容只要三次赋值操作即可，而qsort却要四倍的时间进行(一个整型变量占4个字节)。不过这点差别通常对我们程序的性能影响都不大，不能抵消掉直接使用qsort给我们带来的好处。
二、调用qsort只对数组的部分连续的元素进行快速排序
我们知道C类语言数组的下标是从0开始的，有的时候我们的实际有效数据是从1或者更大的下标开始保存的，这时我们该如何处理呢？有一个办法是将未用到的a[0]使用一个无穷小（从小到大排序）或者无穷大（从大到小排序）进行填充，保证排序前和排序后，a[0]的位置不变。这个办法显然是一个治标不治本的权宜之计，我们还有更好的办法来处理。
我们知道，qsort函数接收的第一个参数其实就是待排序数组的起始地址，而且传递过去后类型都丢失了，所以它几乎就是一个纯净的整数，既然如此，那我们如果传递过去的不是整个数组的首地址，它是不是就不会从a[0]开始排序了呢？答案是：那是当然的！！！你传递的是哪个元素的首地址，它就一定会只从这个元素开始排序。
假设数据结构跟上例完全一致，我们这时只需要对数组a的第3个(a[3])到10个(a[10])元素进行排序，比较函数的定义和上例一样写法，但是调用写法稍改一下即可：
qsort(a+3,8,sizeof(a[0]),compare);
调用后，你会发现，只有a[3]到a[10]被排序了，之前和之后的部分仍旧不变！！！ 三、
结构体数组多关键字排序
有的场合我们需要对一个结构体数组进行多关键字排序，即先按某个字段从小到大排序，但遇到该字段相等的情况，再按第二个字段排序，依此类推。遇到这种情况我们该如何调用qsort函数呢？其实相当简单，我们在写比较函数compare的时候稍稍处理一下就ok了，废话不多说，大家看我写的一个例子就完全明白了，多关键字排序的功能完全在compare函数体内得到了体现。
实例运用
[题目描述]
一共有n个人（以1--n编号）向佳佳要照片，而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序，每人就有了一个序号D[i]（取值同样是1--n）。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1，显然类别序号的取值为1--10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后，最终的权值最大的k个人，并输出他们的编号。权值都是正整数。在排序中，如果两人的W[i]相同，编号小的优先。
[输入格式]
3