深入分析qsort库函数（二）－－std::sort和qsort的比较

在这篇文章，我们把目光投向C++ STL中的函数std::sort。可能有些朋友要奇怪了：不是要讲qsort函数吗，怎么讲起std::sort来了？其实，std::sort是一个改进版的qsort，我们通过分析std::sort，可以了解到qsort函数的优点和不足之处，方便我们更好地理解qsort函数的性质，从而深刻理解快速排序的算法思想。

    我先介绍一下我分析的时候用的源代码。代码很简单，就是一个函数调用，排序随机生成的数组：

#include "stdlib.h"
#include "time.h"
#include <algorithm>
using namespace std;

int A[50];

int _tmain(int argc, _TCHAR* argv[])
{
 int i;
 srand(time(NULL));
 for (i=0;i<50;i++) A[i]=rand();
 std::sort(A,A+50);
 return 0;
}

    在std:sort这一行下一个断点，然后跟踪进去就可以看到如下代码：

template<class _RanIt> inline
 void sort(_RanIt _First, _RanIt _Last)
 { // order [_First, _Last), using operator<
 _Sort(_First, _Last, _Last - _First);
 }

    实际上sort又调用了_Sort函数，我们再跟进：

template<class _RanIt,
 class _Diff> inline
 void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
 { // order [_First, _Last), using operator<
 _Diff _Count;
 for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
  { // divide and conquer by quicksort
  pair<_RanIt, _RanIt> _Mid = _Unguarded_partition(_First, _Last);
  _Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions

  if (_Mid.first - _First < _Last - _Mid.second) // loop on larger half
   _Sort(_First, _Mid.first, _Ideal), _First = _Mid.second;
  else
   _Sort(_Mid.second, _Last, _Ideal), _Last = _Mid.first;
  }

 if (_ISORT_MAX < _Count)
  { // heap sort if too many divisions
  std::make_heap(_First, _Last);
  std::sort_heap(_First, _Last);
  }
 else if (1 < _Count)
  _Insertion_sort(_First, _Last); // small, insertion sort
 }

    代码看起来很简单不是吗？我们逐行来分析一下：

for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )

    这里的_ISORT_MAX定义为32，也就是说，如果子数组的大小小于32，则使用后面的排序方法，而不进行快速排序。我在本系列文章的第一篇里面讲到，qsort函数使用了小子数组截取的方法，这里就是这种方法的体现。但是在sort函数里面又有所不同，它的截取值比较大（qsort中是8）。其实这是因为，在面对比较大的数组时，经过快速排序以后，数组已经基本有序，所以在运行插入排序的时候，只需要很少数量的比较和交换就可以完成排序。对插入排序不是很了解的读者，可以查一下相关的资料。

pair<_RanIt, _RanIt> _Mid = _Unguarded_partition(_First, _Last);

    这里是快速排序的分区工作。我们在这里先跳过，在后面的分析中可以看到，这个分区是一个完全的三路划分分区算法。qsort中也使用了三路划分，不过并不是十分的完全。

  _Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions

    这里的_Ideal，我认为应该是用来控制递归深度的变量。

  if (_Mid.first - _First < _Last - _Mid.second) // loop on larger half
   _Sort(_First, _Mid.first, _Ideal), _First = _Mid.second;
  else
   _Sort(_Mid.second, _Last, _Ideal), _Last = _Mid.first;
  }

    如果看过qsort源代码的朋友应该对上面这里有点感觉吧。这里是和qsort对应的小子数组先处理方法。

 if (_ISORT_MAX < _Count)
  { // heap sort if too many divisions
  std::make_heap(_First, _Last);
  std::sort_heap(_First, _Last);
  }
 else if (1 < _Count)
  _Insertion_sort(_First, _Last); // small, insertion sort
 }

    这个部分是针对小数组或者是达到了递归深度限制的时候使用的排序。当达到了递归深度，就不使用上面的递归快速排序了。这种情况下有两种可能：一种是数组大小还比32要大，另一种是比大小比32小。对前一种情况，使用堆排序。而后一种情况，则使用虽然时间复杂度是二次但对小数组有效的插入排序。

    好了，_Sort这里讲了个大概了。我们下面分_Unguarded_partition函数。由于代码较长，我们在中间插入解释。

template<class _RanIt> inline
 pair<_RanIt, _RanIt> _Unguarded_partition(_RanIt _First, _RanIt _Last)
 { // partition [_First, _Last), using operator<
 _RanIt _Mid = _First + (_Last - _First) / 2; // sort median to _Mid
 _Median(_First, _Mid, _Last - 1);

    这里是调用获得枢轴值的函数。我大概讲一下它的作用，有兴趣的朋友可以跟进里面看看。主要分两种情况，如果数组大小大于40，则把数组分成8份，这样就有9个端点，123，456，789，这样三次三元素排序，然后再258排序，返回5。如果小于40，就只对首、中、尾三元素排序，返回中间值。
 _RanIt _Pfirst = _Mid;
 _RanIt _Plast = _Pfirst + 1;

    上面这两个指针是在算法中最重要的变量。等一下会讲到。

 while (_First < _Pfirst
  && !(*(_Pfirst - 1) < *_Pfirst)
  && !(*_Pfirst < *(_Pfirst - 1)))
  --_Pfirst;

    这个while循环的作用是把_Pfirst指针向前移动，直到遇到和*_Pfirst不等的项为止。这里的作用就是把中间和*_Mid相等的项的分区范围向前拉动。
 while (_Plast < _Last
  && !(*_Plast < *_Pfirst)
  && !(*_Pfirst < *_Plast))
  ++_Plast;

    这里的while循环和前面的差不多，不过要注意的是，前面的指针_Pfirst指向的值始终和*Mid相等；而_Plast指向和*Mid相等的项的后一个。

 _RanIt _Gfirst = _Plast;
 _RanIt _Glast = _Pfirst;

    好了，执行完上面两个循环。这时候在区间[_Pfirst,_Plast-1]里面的所有项都等于枢轴的值。我们再增加了两个指针。这两个指针就是用来交换大值和小值的。

 for (; ; )
  { // partition
  for (; _Gfirst < _Last; ++_Gfirst)
   if (*_Pfirst < *_Gfirst)
    ;
   else if (*_Gfirst < *_Pfirst)
    break;
   else
    std::iter_swap(_Plast++, _Gfirst);

    留意一下这个循环。它的作用是不断移动_Gfirst指针向后寻找比枢轴小的数，找到的时候跳出。注意里面有一个判断*_Gfirst是否等于*_Pfirst的条件分支，如果相等，证明_Gfirst指向的项和枢轴相等（因为*_Pfirst和枢轴相等）。这时，要把它和_Plast指针指向的项交换，我们刚才讲过，和枢轴相等的区间是[_Pfirst,_Plast-1]，因此这个操作相当于把和枢轴相等的一个数又并在了它的区间的右边。然后_Plast向后移动，方便后面继续并入相等值。

  for (; _First < _Glast; --_Glast)
   if (*(_Glast - 1) < *_Pfirst)
    ;
   else if (*_Pfirst < *(_Glast - 1))
    break;
   else
    std::iter_swap(--_Pfirst, _Glast - 1);

    这个循环和上一个作用是一样的，不过有点不同的是_Glast-1这个指针才是指向要判断的项。这是因为一开始的时令_Glast=_Pfirst。这个时候的区间表示如下：

    [_Pfirst , _Plast-1] ＝ *_Mid;

    [_Glast , _Pfirst-1] <   *_Mid;

    [_Plast , _Gfirst-1] >   *_Mid;

    两个指针的情况：*(_Glast-1)>*_Mid;  *_Gfirst<*_Mid;

  if (_Glast == _First && _Gfirst == _Last)
   return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));

    这里是循环退出的惟一条件，即分区完毕。

  if (_Glast == _First)
   { // no room at bottom, rotate pivot upward
   if (_Plast != _Gfirst)
    std::iter_swap(_Pfirst, _Plast);
   ++_Plast;
   std::iter_swap(_Pfirst++, _Gfirst++);
   }

    如果_Glast==_First，即前面已经没有空位了，这里采取的是把枢轴区间向后移动一个位置，方法是把_Pfirst和_Plast指向的项交换。然后交换_Pfirst和_Gfirst指向的项，即再交换一次大值和小值，保持前面介绍的区间状况。注意，在这个循环里面，上面提到的区间情况是始终的到满足的。
  else if (_Gfirst == _Last)
   { // no room at top, rotate pivot downward
   if (--_Glast != --_Pfirst)
    std::iter_swap(_Glast, _Pfirst);
   std::iter_swap(_Pfirst, --_Plast);
   }

    这里是后面没有空位的情况，和前面差不多，我就不多说了。
  else
   std::iter_swap(_Gfirst++, --_Glast);

    如果一切正常，就交换大值和小值，继续循环。
  }
 }

    好了。我们现在分析了std:sort的源代码了，虽然还有些子函数没有讲，但是我们已经可以从大概的情况中了解到了std::sort函数优于qsort的一些特点：对大数组采取9项取样，更完全的三路划分算法，更细致的对不同数组大小采用不同方法排序。这里是对sort函数的定性分析，我尽量在后面的文章做些定量的分析，还有用实验来比较它和qosrt之间的优劣。