基本原理
   快速排序算法是一種分治排序算法，影響其性能的因素有劃分元素的選擇、小的子文件的處理、重復關鍵字等，本文論述針對重復關鍵字的改進實現。首先來回顧下一般的算法實現，其流程如下：
   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)。