3.1. 哪一种排序方法最方便?

3.1. 哪一种排序方法最方便?

     答案是C标准库函数qsort()，理由有以下三点：
    (1)该函数是现成的；    
    (2)该函数是已通过调试的；
    (3)该函数通常是已充分优化过的。
    qsort()函数通常使用快速排序算法，该算法是由C. A．R．Hoare于1962年提出的。以下是qsort()函数的原型：
    void qsort(void *buf，size_t hum，size_t size，
    int(*comp)(const void *ele1，const void *ele2));

    qsort()函数通过一个指针指向一个数组(buf)，该数组的元素为用户定义的数据，数组的元素个数为num，每个元素的字节长度都为size。数组元素的排序是通过调用指针comp所指向的一个函数来实现的，该函数对数组中由ele1和ele2所指向的两个元素进行比较，并根据前者是小于、等于或大于后者而返回一个小于、等于或大于0的值。   
    例3．1中给出了一个函数sortStrings()，该函数就是通过qsort()函数对一个以NULL指针结束的字符串数组进行排序的。将例3．1所示的代码和本章结尾的有关代码一起编译成一个可执行程序后，就能按字母顺序对一个以NULL指针结束的字符串数组进行排序了。

1:#include
 2:
 3: /*
 4:  * This routine is used only by sortStrings(), to provide a
 5:  * string comparison {unction to pass to qsort().
 6:  */
 7: static int comp(const void * elel, const void * ele2)
 8: {
 9:    return strcmp( * (const char * * ) ele1,
10:                * (const char * * ) ele2);
11: }
12:
13: / * Sort strings using the library function qsort() * /
14: void sortStrings(const char * array[-'])
15: {
16,       /* First, determine the length of the array * /
17:       int num;
18:
19:      for (num=O; array[num]; num++)
20:
21:      qsort(array, num, sizeof( * array), comp) ;
22: }

 在例3．1中，第19行和第20行的for循环语句用来计算传递给qsort()函数的数组元素个数，函数comp()的作用是将函数qsort()传递给它的类型(const void *)转换为函数strcmp()
所要求的类型(const char *)。因为在函数qsort()中，ele1和ele2是指向数组元素的指针，而在例3．1中这些数组元素本身也是指针，因此，应该先将ele1和ele2转换为const char **类型，然后在转换结果前加上指针运算符“*”，才能得到函数strcmp()所要求的类型。
    尽管有qsort()函数，但程序员经常还要自己编写排序算法程序，其原因有这样几点：第一，在有些异常情况下，qsort()函数的运行速度很慢，而其它算法程序可能会快得多；第二，qsort()函数是为通用的目的编写的，这给它带来了一些不利之处，例如每次比较时都要通过用户提供的一个函数指针间接调用一个函数；第三，由于数组元素的长度在程序运行时才能确定下来，因此用来在数组中移动数组元素的那部分代码没有针对数组元素长度相同的情况进行优化；第四，qsort()函数要求所有数据都在同一个数组中，而在实际应用中，数据的长度和性质千变万化，可能很难甚至无法满足这一要求；第五，qsort()函数通常不是一种稳定的排序方法。

    请参见：  
    3．2 哪一种排序方法最快?
    3．3 当要排序的数据集因太大而无法全部装入内存时，应怎样排序?
    3．7 怎样对链表进行排序?
    7．1 什么是间接引用(indirection)?
    7，2 最多可以使用几层指针?
    7．5 什么是void指针?    ·
    7．6 什么时候使用void指针?