身上無錢你莫邪

排序一直是數(shù)據(jù)結(jié)構(gòu)中的常用算法，STL提供的排序算法非常豐富，如何有效使用就值得探討。在網(wǎng)上沒有找到條款31的翻譯，于是我自己翻譯了。－－Winter

如何進(jìn)行排序？讓我數(shù)數(shù)有幾種方法。

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

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

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

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

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

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

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

你可以看出，調(diào)用nth_element函數(shù)和調(diào)用partial_sort函數(shù)在本質(zhì)上沒有區(qū)別，唯一的不同在于partial_sort把前20個元素還進(jìn)行排列了，而nth_element并不關(guān)系他們內(nèi)部的順序。兩個算法都實(shí)現(xiàn)了同樣的功能：把質(zhì)量最好的20個元素放在vector容器的開始部分。

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

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

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

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

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

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

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

    …                                                 // goalPosition 現(xiàn)在指向質(zhì)量排在75％的元素。

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

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

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

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

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

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

partition 和stable_partition函數(shù)與sort、stable_sort、partial_sort、nth_element不一樣，要求沒有那么嚴(yán)格，輸入?yún)?shù)只需是雙向迭代器(bidirectional iterator)。因此你可以對所有的標(biāo)準(zhǔn)序列容器使用partition和stable_partition算法。

讓我們來總結(jié)一下你的排序操作：

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

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

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

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

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

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

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

• 1. partition

• 2. stable_partition

• 3. nth_element

• 4. partial_sort

• 5. sort

• 6. stable_sort

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