Effective STL 條款 31：理解你的排序選項——從全排序到分區的完整指南

STL 提供六大排序相關演算法，各有適用場景與效能特性。本文依照《Effective STL》條款 31 脈絡，系統比較 sort、stable_sort、partial_sort、nth_element、partition、stable_partition，並給出決策流程圖與容器相容性表。

六大演算法速查表

決策流程：你需要哪一個？

需要完整有序序列？
├─ 是 → 需穩定？ → 是 → stable_sort
│            └─ 否 → sort
└─ 否 → 只需前 K 小且有序？ → partial_sort
      → 只需第 K 小/中位數/百分位？ → nth_element
      → 只需滿足條件者集中在前？ → 需穩定？ → stable_partition
                                            └─ 否 → partition

程式碼範例：Widget 品質篩選

bool qualityCompare(const Widget& a, const Widget& b) { return a.quality() > b.quality(); }
bool isPremium(const Widget& w) { return w.quality() >= PREMIUM_THRESHOLD; }

vector widgets = ...;

// 1. 取品質前 20 並內部排序
partial_sort(widgets.begin(), widgets.begin()+20, widgets.end(), qualityCompare);

// 2. 只取前 20 不需內部排序
nth_element(widgets.begin(), widgets.begin()+20, widgets.end(), qualityCompare);

// 3. 找中位數品質
auto mid = widgets.begin() + widgets.size()/2;
nth_element(widgets.begin(), mid, widgets.end(), qualityCompare);

// 4. 找品質前 25% 門檻
auto p25 = widgets.begin() + widgets.size()/4;
nth_element(widgets.begin(), p25, widgets.end(), qualityCompare);

// 5. 將優質品集中在前（不保證內部順序）
auto goodEnd = partition(widgets.begin(), widgets.end(), isPremium);

// 6. 同上但保持優質品內部原序
auto goodEnd = stable_partition(widgets.begin(), widgets.end(), isPremium);

容器相容性補充

• RandomAccess 迭代器容器：vector、deque、string、array → 支援所有六大演算法。
• list：雙向迭代器 → 僅支援 partition/stable_partition；list::sort() 內建穩定排序；需 partial_sort/nth_element 時，複製到 vector 處理再回寫。
• 關聯容器 (set/map...)：本身有序，無需額外排序。
• priority_queue：隱式堆有序，適合持續取極值。

partition < stable_partition < nth_element < partial_sort < sort < stable_sort