STL 排序算法全解析：從 sort 到 partition 的選擇藝術

前言：為何必須精通 STL 排序

排序是程式設計中最高頻算法之一。STL（標準模板庫）提供了高效、泛型、經過嚴格測試的排序組件，讓開發者脫離底層算法實現細節，專注業務邏輯。本文系統梳理 STL 所有排序算法的特性、適用場景與選擇策略。

核心排序算法總覽

所有排序算法接受迭代器範圍 [first, last)，要求**隨機存取迭代器**（除 partition/stable_partition 外）。支援自定義比較函數（仿函數）。

比較函數與仿函數

預設使用 std::less<T>（即 operator<）。常用仿函數：

• less<T>、greater<T>、less_equal<T>、greater_equal<T>
• equal_to<T>、not_equal_to<T>

自定義類型可：

1. 重載 operator<
2. 編寫獨立比較函數/仿函數傳遞給算法

穩定性的實際意義

「穩定」指**相等元素（按比較函數判定相等）相對順序不變**。例如按字串長度排序時，"apple" 與 "winter" 長度相同，stable_sort 保證原順序，sort 可能打亂。

算法深度解析與實戰選擇指南

全量排序：sort vs stable_sort

• sort：IntroSort（快排+堆排+插排混合），平均 O(N log N)，最壞 O(N log N)，**不穩定**，速度最快。
• stable_sort：歸併排序，穩定，需額外記憶體，記憶體充足時 O(N log N)，否則 O(N log²N)。

部分排序：partial_sort / partial_sort_copy

• 只需前 M 個最小元素有序時使用，堆排序實現，O(N log M)。
• partial_sort_copy 適合輸入為單向迭代器或需保留原容器場景。

定位第 N 元素：nth_element

• 只關心第 N 位置元素，不關心兩側順序。平均 O(N)，比部分排序更快。
• 典型場景：尋找中位數、Top K 問題（配合 partition）。

分區算法：partition / stable_partition

• 將滿足條件的元素移至前段，不保證區內順序。
• 非排序，而是「分類」，複雜度 O(N)，極快。
• 適用：分離正負數、及格/不及格、奇偶數等二分類場景。

容器相容性總結

• vector, string, deque, array：支援所有隨機存取算法。
• list：無隨機迭代器，**不可用**標準算法。使用成員函數 list::sort()（指針操作、迭代器不失效）、list::merge()、list::remove_if() 等。需 partial_sort/nth_element 時，先複製到 vector。
• set, map, multiset, multimap：內部紅黑樹**天然有序**，無需額外排序。

效率與選擇決策樹

按執行速度由快到慢（同等條件下）：

1. partition / stable_partition — O(N)
2. nth_element — 平均 O(N)
3. partial_sort — O(N log M)
4. sort — O(N log N)
5. stable_sort — O(N log N) ~ O(N log²N)

Effective STL 選擇原則：

• 全量排序 → sort（不需穩定）或 stable_sort（需穩定）
• Top N → partial_sort
• 第 N 元素 / Top N 不需內部有序 → nth_element
• 條件分區 → partition / stable_partition
• list 容器 → 成員函數或複製到 vector

結語

選對算法不僅關乎效能，更體現代碼意圖清晰度。理解每個算法的複雜度、穩定性、迭代器要求與適用場景，是 C++ 開發者進階的必修課。