排序一直是數據結構中的常用算法，STL提供的排序算法非常豐富，如何有效使用就值得探討。在網上沒有找到條款31的翻譯，于是我自己翻譯了。－－Winter

如何進行排序？讓我數數有幾種方法。

一旦程序員需對容器元素進行排序，sort算法馬上就會出現在他的腦海(可能有些程序員會想到qsort，但詳細閱讀條款46后，他們會放棄使用qsort的想法，轉而使用sort算法)。

sort是一個非常優秀的算法，但并當你并不真正需要它的時候，其實就是一種浪費。有時你并不需要一個完整的排序（簡稱為全排序）。例如，你現有一個包含Widget對象（Widget意為“小掛件”）的vector容器，并且你想把其中質量最好的20個Widget送給你最好的客戶，那么你需做的只是找出這20個質量最好的Widget元素，剩下的并不需關心它們的順序。這時你需要的是部分排序（相對于全排序），恰好在算法中就有一個名副其實的部分排序函數函數：partial_sort：

 bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
            // lhs的質量不比rhs的質量差時返回true，否則返回false
}
…
partial_sort (widgets.begin(),                         // 把質量最好的20元素
                    widgets.begin() + 20,                 // 順序放入widgets容器中
                    widgets.end(),                            
                    qualityCompare);
…                                                                 // 使用 widgets...

通過調用partial_sort，容器中開始的20個元素就是你需要的質量最好的20個Widget，并按順序排列，質量排第一的就是widgets[0], 緊接著就是widgets[1]，依次類推。這樣你就可以把質量第一的Widget送給你最好的顧客，質量第二的Widget就可以送給下一個顧客，很方便吧，更方便的還在后面呢。

如果你只是想把這20個質量最好的Widget禮物送給你最好的20位顧客，而不需要給他們一一對應，partial_sort在這里就有些顯得大材小用了。因為在這里，你只需要找出這20個元素，而不需要對它們本身進行排序。這時你需要的不是partial_sort，而是nth_element。

nth_element排序算法只是對一個區間進行排序，一直到你指定的第n個位置上放上正確的元素為止，也就是說，和你進行全排序和nth_element排序相比，其共同點就是第n個位置是同一個元素。當nth_element函數運行后，在全排序中應該在位置n之后的元素不會出現在n的前面，應該在位置n前面的元素也不會出現在n的后面。聽起來有些費解，主要是我不得不謹慎地使用我的語言來描述nth_element的功能。別著急，呆會兒我會給你解釋為什么，現在先讓我們來看看nth_element是如何讓質量最好的20個widget禮物排在vector容器的前面的：

nth_element (widgets.begin(),             // 把質量最好的20元素放在
                      widgets.begin() + 20,     // widgets容器的前面,
                      widgets.end(),                // 但并不關心這20個元素
                      qualityCompare);            //本身內部的順序

你可以看出，調用nth_element函數和調用partial_sort函數在本質上沒有區別，唯一的不同在于partial_sort把前20個元素還進行排列了，而nth_element并不關系他們內部的順序。兩個算法都實現了同樣的功能：把質量最好的20個元素放在vector容器的開始部分。

這樣引起了一個重要的問題：要是質量一樣的元素，排序算法將會如何處理呢？假設有12個元素的質量都為1（最好等級），15個元素的質量等級為2（質量次之），如果要選擇20個最好的Widget，則先選12個質量為1的元素，然后從15個中選出8個質量為2的元素。到底nth_element和partial_sort如何從15個中選出8個，依據何在？換句話說，當多個元素有同樣的比較值時，排序算法如何決定誰先誰后？

對于partial_sort和nth_element算法來說，你無法控制它們，對于比較值相同的元素它們想怎么排就怎么排（查看條款19，了解兩個值相等的定義）。在我們上面的例子中，面對需要從15個等級為2的元素選出8個增加到top 20中去，他們會任意選取。這樣做也有它的道理：如果你要求得到20個質量最好的Widget，同時有些Widget的質量又一樣，當你得到20個元素至少不比剩下的那些質量差，這已經達到你的要求，你就不能抱怨什么了。

假如對于全排序，你倒是可以得到更多的控制權。一些排序算法是“穩定的”(stable)，在一個“穩定”的排序算法中，如果兩個元素有相同的值，它們的相對位置在排序后也會保持不變。例如：如果在未排序時Widget A在Widget B之前，而且都有相同的質量等級，那么“穩定”排序算法就可以保證在排序之后，Widget A仍然在Widget B之前。而非“穩定”排序算法就不能保證這一點。

partial_sort和nth_element都不是“穩定”排序算法，真正的“穩定”排序算法是stable_sort，從名字上看就知道它是“穩定”的。如果你在排序的時候需要保證相同元素的相對位置，你最好使用stable_sort，在STL中沒有為partial_sort和nth_element算法提供對應的“穩定”版本。

說到nth_element，名字確實很怪，但是功能卻是不少，除了讓你找到無關順序的top n個元素外，它還能找到某個范圍的中值，或者找到在某個特定百分點的值。

    vector<Widget>::iterator begin(widgets.begin());     // widgets的第一個
    vector<Widget>::iterator end(widgets.end());           //和最后一個迭代器
                                                                                      //
    vector<Widget>::iterator goalPosition;                      // 需要定位的那個迭代器
    

      //以下代碼用來得到質量排在中間的那個元素的迭代器
    goalPosition = begin + widgets.size() / 2;             // 要找的那個元素應該
                                                                                 //在vector的中部。
    nth_element(begin, goalPosition, end,         // 找到容器widgets元素的中值
                        qualityCompare);                      //
    …                                                                     // goalPosition現在指向中值元素
   
    //以下代碼用來得到質量排在75%的元素
    vector<Widget>::size_type goalOffset =               // 計算出要找的值
                                        0.25 * widgets.size();         //離begin迭代器的距離。
                                                                                  //  
    nth_element( begin, begin + goalOffset, end,       // 得到質量排在75％的元素
                            qualityCompare);                           //
　

    …                                                 // goalPosition 現在指向質量排在75％的元素。

當你需要把一個集合由無序變成有序時，可選用sort, stable_sort或partial_sort，當你只需得到top n或者在某個特定位置的元素，你就可以使用nth_element。或許有時你的需求比nth_element提供的還要少，例如：你并不需要得到質量最好的前20個Widget，而只需要識別那些質量等級為1或者等級為2的Widget。當然，你可以對整個vector按照Widget的質量等級進行全排序，然后查找到第一個質量等級低于等級2的元素。

問題就在于全排序太耗費資源，而且大部分工作都是無用功。這種情況下最好選擇partition算法，partition只是給你確定一個區間，把符合特定條件的元素放到這個區間中。舉例來說，要把質量等級好于等于等級2的Widget的元素放在widget容器的前端，我們可以定義一個用于識別Widget質量等級的函數：

    bool hasAcceptableQuality(const Widget& w)
    {
        //如果w的質量等于或好于2，返回true，否則返回false
    }

然后把這個判斷函數傳遞給partion算法：
    vector<Widget>::iterator goodEnd =   // 把所有滿足hasAcceptableQuality
                    partition(widgets.begin(),     // 條件的放在widgets容器的前面，
                    widgets.end(),                     // 返回第一個不滿足條件的
                    hasAcceptableQuality);       //元素的位置

這樣一來，所有在迭代器widgets.begin()和迭代器goodEnd之間的元素都是滿足需求的元素：其質量等級好于或等于2。而在 goodEnd 到 widgets.end() 之間的元素的質量等級都會低于質量等級2。如果你對質量等級相同元素的相對位置很關心的話，你可以選擇stable_partition算法來代替partition。

需要注意的是sort, stable_sort, partial_sort, 和nth_element算法都需要以隨機迭代器(random access
iterators)為參數，因此這些算法能只能用于vector, string, deque, 和array等容器，對于標準的關聯容器map、set、multmap、multset等，這些算法就有必要用了，這些容器本身的比較函數使得容器內所有元素一直都是有序排列的。對于容器list，看似可以用這些排序算法，其實也是不可用的（其iterator的類型并不是隨機迭代器），不過在需要的時候可以使用list自帶的排序函數sort(有趣的是list::sort函數和一個“穩定”排序函數的效果一樣)。如果你想對一個list容器使用partial_sort或nth_element，你只能間接使用。一個可選的方法是把list中的元素拷貝到帶有隨機迭代器的容器中，然后再使用這些算法；另一種是生成一個包含list::iterator的容器，直接對容器內的list::iterator進行排序，然后通過list::iterator得到所指的元素；第三種方法，借助一個包含iterator的有序容器，然后反復把list中的元素連接到你想要鏈接的位置。看見了吧，你可以選擇的方式還是比較多的。

partition 和stable_partition函數與sort、stable_sort、partial_sort、nth_element不一樣，要求沒有那么嚴格，輸入參數只需是雙向迭代器(bidirectional iterator)。因此你可以對所有的標準序列容器使用partition和stable_partition算法。

讓我們來總結一下你的排序操作：

• 若需對vector, string, deque, 或 array容器進行全排序，你可選擇sort或stable_sort；

• 若只需對vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首選.

• 若對于vector, string, deque, 或array容器，你需要找到第n個位置的元素或者你需要得到top n且不關系top n中的內部順序，nth_element是最理想的；

• 若你需要從標準序列容器或者array中把滿足某個條件或者不滿足某個條件的元素分開，你最好使用partition或stable_partition；

• 若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必須間接使用。正如上面介紹的有幾種方式可以選擇。

另外，你可以使用標準的關聯容器來保證容器中所有元素在操作過程中一直有序。你還可考慮非標準的STL容器priority_queue，它同樣可以保證其元素在所有操作過程中一直有序(priority_queue在傳統意義上屬于STL的一部分，但根據“STL”定義，需要STL容器支持迭代器，而priority_queue并不支持迭代器，故不能能稱為標準STL容器)。

這時你或許會問：“性能如何？”非常好的問題。廣義的講，算法做的工作越多，花的時間越長，“穩定”性排序算法比“非穩定”性排序算法要耗時。我們可以按照其消耗的資源(時間和空間)的多少，對本文中討論的排序算法作個排序，消耗資源越少的排在前面：

• 1. partition

• 2. stable_partition

• 3. nth_element

• 4. partial_sort

• 5. sort

• 6. stable_sort

選擇這些算法的依據是你的需求而不是它們的性能。若你能選擇一個算法恰好滿足你的需求(如用部分排序代替全排序)，不僅會清晰表達你的意圖，而且能高效的使用STL。