• 首页 »
• 资源下载
• »
• C++培训中心
• »
• 技术文章

快速排序 Gnu glibc qsort

［来源］ 达内    ［编辑］ 达内   ［时间］2012-10-16

先从一个小例子开始,这个例子是使用C library中的qsort函数完成一个数组的排序

先从一个小例子开始,这个例子是使用C library中的qsort函数完成一个数组的排序:

< div style="color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; " class="cnblogs_Highlighter">

< div style="border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border-bottom-right-radius: 0px !important; border-bottom-left-radius: 0px !important; background-image: none !important; border: none !important; bottom: auto !important; float: none !important; height: 11px !important; left: auto !important; line-height: 2em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: absolute !important; right: 1px !important; text-align: left !important; top: 1px !important; vertical-align: baseline !i mportant; width: 11px !important; box-sizing: content-box !important; font-family: 'Courier New', Consolas, 'Bitstream Vera Sans Mono', Courier, monospace !important; font-weight: normal !important; font-style: normal !important; font-size: 10px !important; min-height: inherit !important; z-index: 10 !important; color: rgb(255, 255, 255) !important; background-position: initial initial !important; background-repeat: initial initial !important; " class="toolbar"> ?

< table cellspacing="0" cellpadding="0" border="0" style="border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border-bottom-right-radius: 0px !important; border-bottom-left-radius: 0px !important; background-image: none !important; border: 1px solid rgb(192, 192, 192); bot tom: auto !important; float: none !important; height: auto !important; left: auto !important; line-height: 2em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; text-align: left !im portant; top: auto !important; vertical-align: baseline !important; width: 918px; box-sizing: content-box !important; font-family: 'Courier New', Consolas, 'Bitstream Vera Sans Mono', Courier, monospace !important; font-weight: normal !important; font-style: normal !important; font-size: 12px !important; min-height: inherit !important; border-collapse: collapse; background-position: initial initial !important; background-repeat: initial initial !important; ">

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

/* qsort example */

#include <stdio.h>

#include <stdlib.h>

 

int  values[] = { 40, 10, 100, 90, 20, 25 };

 

int  compare ( const  void  * a, const  void  * b)

{

   return   ( *( int *)a - *( int *)b );

}

 

int  main ()

{

   int  n;

   qsort   (values, 6, sizeof ( int ), compare);

   for  < code style="border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border-bottom-right-radius: 0px !important; border-bottom-left-radius: 0px !important; background-image: none !important; border: 0px !important; bottom: auto !important; float: none !important; height: auto !important; left: auto !important; line-height: 2em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; text-align: left !important; top: auto !important; vertical-align: baseline !i mportant; width: auto !important; box-sizing: content-box !important; font-family: 'Courier New', Consolas, 'Bitstream Vera Sans Mono', Courier, monospace !important; font-weight: normal !important; font-style: normal !important; font-size: 12px !important; min-height: inherit !important; white-space: pre-wrap; color: rgb(0, 0, 0) !important; background-position: initial initial !important; background-repeat: initial initial !important; " class="cpp plain">(n=0; n<6; n++)

      printf   ( "%d " ,values[n]);

   return   0;

}

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">代码如上,这不是我写的,上面提供的实例代码,不用质疑了. 注意一下这种使用的方法,

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">好吧,qsort函数参数中需要一个compare形式的函数指针,猜想一个结论:qsort函数的源码中,排序的方向

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">是不固定的,也就是说根据用户提供的比较函数来定,那么这个函数指针做的任务就只是确定排序方向吗?另外,

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">如果就是简单的确定方向问题,那么为什么不采用使用固定函数参数的形式呢?例如提供使用一个整形参数,

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">然后判断参数就确定排序方向. ... 这些都是我的猜想,要想知道答案,就需要看一下源码.

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "> 

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">qsort函数式是C标准库中的函数,我们也都知道C标准以及变种,我最熟悉的就是GNU C.所以今天的qsort函数

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">源码来自GLIBC.另外有一天需要说明,看到很多网友在说qsort函数的时候就直接将Qsort.c的源码贴出来翻译

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">一下英文注解就完了.我不知道这种做法对不对,也不去评论.但是在本文中,我将会啰嗦一下,说一下是如何找到

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">函数源码的.(下面就是Qsort.c的源码,感兴趣的可以先看一下.)

< div style="background-color: rgb(245, 245, 245); font-family: 'Courier New'; font-size: 12px; border: 1px solid rgb(204, 204, 204); padding: 5px; overflow: auto; margin: 5px 0px; color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; " class="cnblogs_code"> View Code

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "> 

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">　《C标准库》这本书中有讲解qsort函数,感兴趣的可以看看这本书,了解一下C标准库也不错,熟悉一下函数.

< p style="margin: 10px auto; text-indent: 0px; color: rgb(0, 0, 0); font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; ">如果没有这本书,那么获取标准库函数也可以使用WIKI,途径还是蛮多的.下面就不多说了,直入正题吧.

< div style="background-color: rgb(245, 245, 245); font-family: 'Courier New'; font-size: 12px; border: 1px solid rgb(204, 204, 204); padding: 5px; overflow: auto; margin: 5px 0px; color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20px; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; " class="cnblogs_code">

1

 /* Sort NMEMB elements of BASE, of SIZE bytes each, 
2    using COMPAR to perform the comparisons.  
*/3
 extern

 void qsort (void
 *

__base, size_t __nmemb, size_t __size, 4
            __compar_fn_t __compar) __nonnull ((1

, 4)); 
5 #ifdef __USE_GNU 
6

 extern void
 qsort_r (void

 *__base, size_t __nmemb, size_t __size, 7
              __compar_d_fn_t __compar, void *__arg) 
8   __nonnull ((1
, 4

)); 9
 

#endif

1
 void

2 qsort (void
 *b, size_t n, size_t s, __compar_fn_t cmp) 3
 

{ 4   return
 qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); 5 }

  1

 void

  2 qsort_r (void
 *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) 
  3 { 
  4

   size_t size = n * s;   5
   char

 *tmp = NULL;   6
   struct msort_param p; 
  7

 
  8   /*
 For large object sizes use indirect sorting.  */

  9   if
 (s > 32) 
 10

     size = 2 * n * sizeof
 (void *) + s; 
 11

 
 12   if
 (size < 1024) 
 13

     /* The temporary array is small, so put it on the stack.  
*/

 14     p.t = __alloca (size); 
 15   else

 16     { 
 17       /*


 We should avoid allocating too much memory since this might  18 
     have to be backed up by swap space.  

*/

 19       static
 long int
 phys_pages; 

 20       static
 int pagesize; 
 21

 
 22       if
 (phys_pages == 0) 
 23

     {  24
       phys_pages = __sysconf (_SC_PHYS_PAGES);  25
 
 26       if
 (phys_pages == -1) 
 27

         /* Error while determining the memory size.  So let's 
 28            assume there is enough memory.  Otherwise the 
 29            implementer should provide a complete implementation of 
 30            the `sysconf' function.  
*/ 31
         phys_pages = (long

 int) (~0ul
 >> 1

);  32
 
 33       /*
 The following determines that we will never use more than  34
          a quarter of the physical memory.  */

 35       phys_pages /= 4
;  36
 
 37       pagesize = __sysconf (_SC_PAGESIZE); 
 38     } 


 39
 
 40       /*
 Just a comment here.  We cannot compute  41
 

       phys_pages * pagesize  42 
       and compare the needed amount of memory against this value.  43 
       The problem is that some systems might have more physical  44 
       memory then can be represented with a `size_t' value (when 

 45        measured in bytes.  
*/

 46 
 47       /*
 If the memory requirements are too high don't allocate memory.  */

 48       if
 (size / pagesize > (size_t) phys_pages)  49
 

    {  50       _quicksort (b, n, s, cmp, arg); 
 51       return


;  52     } 
 53
 
 54       /*
 It's somewhat large, so malloc it.  */

 55       int
 save = errno;  56
       tmp = malloc (size); 

 57       __set_errno (save); 
 58       if
 (tmp == NULL) 

 59     { 
 60       /*


 Couldn't get space, so use the slower algorithm  61 
         that doesn't need a temporary array.  

*/

 62 
      _quicksort (b, n, s, cmp, arg);  // 这里才调用Qsort.c中的 _quicksort函数.  63
       return

;  64
     } 

 65       p.t = tmp; 
 66     } 
 67

 
 68   p.s = s; 
 69   p.var
 = 4

;  70
   p.cmp = cmp;  71
   p.arg = arg; 

 72
 
 73   if
 (s > 32) 
 74

     {  75
       /* Indirect sorting.  
*/ 76
       char

 *ip = (char *) b; 
 77

       void **tp = (void
 **) (p.t + n * sizeof (void
 *)); 

 78       void
 **t = tp;  79
       void

 *tmp_storage = (void *) (tp + n); 
 80
 
 81       while
 ((void *) t < tmp_storage) 
 82

     {  83
       *t++ = ip;  84
       ip += s; 

 85     } 
 86       p.s = sizeof
 (void

 *);  87
       p.var

 = 3; 
 88       msort_with_tmp (&p, p.t + n * sizeof
 (

void *), n);  89
 
 90       /*
 tp[0] .. tp[n - 1] is now sorted, copy around entries of  91
      the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */

 92       char
 *kp;  93
       size_t i; 

 94       for
 (i = 0, ip = (char
 *) b; i < n; i++, ip += s) 

 95     if
 ((kp = tp[i]) != ip)  96
       { 

 97         size_t j = i; 
 98         char
 *jp = ip; 

 99         memcpy (tmp_storage, ip, s); 
100
 
101         do
102           { 
103         size_t k = (kp - (char
 *) b) /

 s; 104         tp[j] = jp; 
105         memcpy (jp, kp, s); 


106         j = k; 107
         jp = kp; 108
         kp =

 tp[k]; 109           } 
110         while
 (kp != ip); 

111
 
112         tp[j] = jp; 
113         memcpy (jp, tmp_storage, s); 


114       } 115
     } 116
   else117
     { 

118       if
 ((s & (sizeof

 (uint32_t) - 1)) == 0

119       && ((char
 *) b - (char *) 0
) % __alignof__ (uint32_t) == 0) 
120

     { 121
       if

 (s == sizeof (uint32_t)) 
122         p.var
 = 0

; 123
       else if
 (s == sizeof

 (uint64_t) 124
            && ((char *) b - (char
 *) 0

) % __alignof__ (uint64_t) == 0) 
125         p.var
 = 1

; 126
       else

 if ((s & (sizeof
 (unsigned long) - 1
)) == 0127
            && ((char

 *) b - (char *) 0
) 

128               % __alignof__ (unsigned long
) == 0) 
129

         p.var = 2
; 130
     } 

131       msort_with_tmp (&p, b, n); 
132     } 
133

   free (tmp); 134 }

 1

 nonnull (arg-index, ...)  2
 The nonnull attribute specifies that some function parameters should be non-null
 pointers. For instance, the declaration: 

 3           extern
 void

 *
 4           my_memcpy (void
 *dest, const void
 *

src, size_t len)  5                   __attribute__((nonnull (1
, 2))); 


 6
      
 7 causes the compiler to check that, in
 calls to my_memcpy, arguments dest and src are non-null
. If the compiler determines 
   that a null pointer is
 passed in an argument slot marked as
 non-

null, and the -Wnonnull option is enabled, a warning is
 issued. 
   The compiler may also choose to make optimizations based on the knowledge that certain function arguments will not be null
.  8
 
 9 If no argument index list is
 given to the nonnull attribute, all pointer arguments are marked as non-null
. To illustrate,
    the following declaration is equivalent to the previous example: 
10
 
11           extern
 void
 *
12           my_memcpy (void
 *dest, const void
 *

src, size_t len) 13                   __attribute__((nonnull));

1
 Cdefs.h (misc\sys):# define __nonnull(params) __attribute__ ((__nonnull__ params
))

1
 typedef int (*__compar_fn_t) (__const void
 *, __const void *);