这是最好的时代，这是最坏的时代。   

                                                                ——狄更斯

    当在pascal里埋头苦干的前辈们还在为快排和堆排哪个效率更高争吵不休时，我们拥有了qsort。

    当我还在为qsort里最后一个参数愁眉苦脸时，STL的工程师们发明了sort。

                                                               ——Crux.D

    qsort(array,asize,sizeof(elem),elem_compare);   很简单的四个参数。第一个参数是待排序的数组，第二个是数组的长度，接着是数组里元素的大小，最后一个参数是一个函数 void elem_compare——他的两个参数是限定的：  const void *a, const void *b。换句话说，qsort是通用的，所以它可以用于不同容器类型、元素类型、比较方式的任意有意义的组合。

    最简单的int数组。从小到大排序。即

int num[100];

int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

qsort(num,100,sizeof(num[0]),cmp); 

    实际上是这样的：

 int *A = ( int* ) a;    //强制转化
 int *B = ( int* ) b;
 return *A - *B;    

    比如一个结构体。对x排序，若x相同，则对y排序。

typedef struct
{
 int x, y;
} Point;
Point pt[100];

    那么如何写elem_compare？

    同样，首先进行元素类型的强制转化。

 Point *A = ( Point* ) a;
 Point *B = ( Point* ) b;

     现在A和B是两个Point型的指针。

 if ( A->x == B->x ) return ( A->y > B->y );
 else return ( A->x > B->x );

    是不是有点麻烦？那么改用STL中的sort试试看。

    对于int数组，sort非常简单。

sort ( num , 100 );

    而对于结构体，需要重载operator。

struct pt_cmp
{
 bool operator () ( const Point &a, const Point &b ) const
 {
  if ( a.x == b.x ) return a.y < b.y;
  return a.x < b.x;
 }
};

sort ( pt, pt + 4, pt_cmp () );

    而且，很多人欣赏sort()是因为它是类型安全的，使用它不需要进行造型（cast），没有人必须去为基本类型写一个compare()函数。

评论