C++ STL標準庫這麼多排序函數，該如何選擇？

通過前面的學習我們知道，C++ STL 標準庫共提供了 4 種排序函數，這裡先帶大家回顧一下，如表 1 所示。

表 1 C++ STL排序函數

排序函數	功能
sort()	對指定範圍內所有的資料進行排序，排序後各個元素的相對位置很可能發生改變。
stable_sort()	對指定範圍內所有的資料進行排序，並確保排序後各個元素的相對位置不發生改變。
partial_sort()	對指定範圍內最大或最小的 n 個元素進行排序。
nth_element()	調整指定範圍內元素的儲存位置，實現位於位置 n 的元素正好是全排序情況下的第 n 個元素，並且按照全排序規則排在位置 n 之前的元素都在該位置之前，按照全排序規則排在位置 n 之後的元素都在該位置之後。

關於以上 4 種排序函數各自的用法，讀者可閱讀之前的文章，這裡不再過多贅述。

值得一提的是，以上 4 種排序函數在使用時，都要求傳入隨機存取疊代器，因此這些函數都只適用於 array、vector、deque 以及普通陣列。

當操作物件為 list 或者 forward_list 序列式容器時，其容器模板類中都提供有 sort() 排序方法，藉助此方法即可實現對容器內部元素進行排序。其次，對關聯式容器（包括雜湊容器）進行排序是沒有實際意義的，因為這類容器會根據既定的比較函數（和雜湊函數）維護內部元素的儲存位置。

那麼，當需要對普通陣列或者 array、vector 或者 deque 容器中的元素進行排序時，怎樣選擇最合適（效率最高）的排序函數呢？這裡為大家總結了以下幾點：

1. 如果需要對所有元素進行排序，則選擇 sort() 或者 stable_sort() 函數；
2. 如果需要保持排序後各元素的相對位置不發生改變，就只能選擇 stable_sort() 函數，而另外 3 個排序函數都無法保證這一點；
3. 如果需要對最大（或最小）的 n 個元素進行排序，則優先選擇 partial_sort() 函數；
4. 如果只需要找到最大或最小的 n 個元素，但不要求對這 n 個元素進行排序，則優先選擇 nth_element() 函數。

除此之外，很多讀者都關心這些排序函數的效能。總的來說，函數功能越複雜，做的工作越多，它的效能就越低（主要體現在時間複雜度上）。對於以上 4 種排序函數，綜合考慮它們的時間和空間效率，其效能之間的比較如下所示：

nth_element() > partial_sort() > sort() > stable_sort()       <--從左到右，效能由高到低

建議大家，在實際選擇排序函數時，應更多從所需要完成的功能這一角度去考慮，而不是一味地追求函數的效能。換句話說，如果你選擇的演算法更有利於實現所需要的功能，不僅會使整個程式碼的邏輯更加清晰，還會達到事半功倍的效果。