基本原理
   快速排序算法是一种分治排序算法，影响其性能的因素有划分元素的选择、小的子文件的处理、重复关键字等，本文论述针对重复关键字的改进实现。首先来回顾下一般的算法实现，其流程如下：
   a. 选择一个划分元素，这个元素在划分后将在最终的位置上，通常是选择最右端元素作为划分点。
   b. 从左端开始扫描，直到找到大于划分元素的元素；同时从右端开始扫描，直到找到小于划分元素的元素，再交换使扫描停止的这两个元素。
   c. 继续步骤b，直到左指针不小于右指针，最后再交换左指针元素和划分元素。
   d. 在左指针左侧和右侧区间(区间不包括左指针元素)重复以上过程，直至元素个数为0或1。
   在划分的过程中，位于左指针左侧的元素都比划分元素小，右侧的元素都比划分元素大，如下图所示    由上述可见，一般的算法实现针对大量重复关键字的输入情况，其性能表现很差，例如如果一个文件完全由相等的值(只有一个值)组成，那么它就不需要再进行任何排序，但前面的算法依然划分直至得到小的子文件，无论文件有多大。针对这一情况，可以作实质性的改进，从而避免处理元素相同的子区间，提高效率。改进的算法实现主要问题在于如何处理与划分元素相等的情况，这里的基本思想是将区间划分为三个部分，左部分小于划分元素，中间部分等于划分元素，右部分大于划分元素，然后再在左右两部分进行子处理，具体的流程如下：
   a'. 选择左端元素、中间元素和右端元素的中值作为划分元素，也就是三者取中划分，这样能有效避免划分区间的最坏情况。
   b'. 从左端开始扫描，直到找到不小于划分元素的元素；同时从右端开始扫描，直到找到不大于划分元素的元素，再交换使扫描停止的这两个元素。如果左指针元素等于划分元素，那么与左端的元素交换，并递增左端位置(初始化为文件最左位置)；如果右指针元素等于划分元素，那么与右端元素交换，并递减右端位置(初始化为文件最右位置)。
   c'. 继续步骤b'，直到左指针不小于右指针。
   d'. 交换最左端区间和左指针左侧区间(不包括左指针元素)，这一过程会递减左端位置；交换最右端区间和左指针右侧区间(包括左指针元素)，这一过程会递增右端位置。
   e'. 在最左端和最右端区间重复以上过程，直至元素个数为0或1。
   在划分的过程中，与划分元素相等的元素分布在最左端和最右端，如下图所示    在划分完成后处理子文件前，需要对调区间，如步骤d'所述，结果如下图所示
代码实现
   上面所有图中的v代表划分元素，最后列出代码清单，函数quick_sort有两个版本，一个是支持operator < 的默认实现，另一个是支持带谓词的自定义比较实现。在其中用到了实现三者取中值的__median函数，对应的也有两个版本实现，如下所示    从上面实现可看出，与一般的实现相比，划分过程多了两个if及for循环，if测试用来将找到的重复元素放在左右两端；for循环用来交换区间，将重复元素再放在中间，这额外的工作量只与找到的重复关键字的个数成线性，因此，即使在没有重复关键字的情况下，它也运行得很好，平均时间复杂度为O(NlgN)。