一、STL 算法
C++的STL（Standard Template Library） 提供了一組高效、通用的算法，這些算法適用于各種容器（如 vector、list、set、map）。
這些算法主要位于 <algorithm> 和 <numeric> 頭文件中。
- 通用性：適用于所有 STL 容器，如
vector、list、deque等。 - 高效性：內部使用優化算法（如快速排序
std::sort）。 - 一致性：所有算法都基于迭代器操作，使其與不同容器兼容。
- 可組合性：可結合
lambda表達式、bind、function object使用。
二、STL 算法分類
STL 算法可分為以下幾類：
| 類別 | 常見算法 | 作用 |
|---|---|---|
| 排序 | sort、stable_sort、partial_sort、nth_element等 | 排序 |
| 搜索 | find、find_if、count、count_if、binary_search等 | 查找元素 |
| 修改 | copy、replace、replace_if、swap、fill等 | 修改容器內容 |
| 刪除 | remove、remove_if、unique等 | 刪除元素 |
| 歸約 | for_each、accumulate等 | 處理數據 |
| 合并 | merge、set_union、set_intersection等 | 處理有序序列 |
| 排列組合 | next_permutation、prev_permutation等 | 生成排列 |
| 堆操作 | push_heap、pop_heap、make_heap、sort_heap等 | 處理堆 |
三、STL 排序算法
STL 提供了一些常用的排序算法，用于對容器中的元素進行排序。
它們位于 <algorithm> 頭文件中。
| 算法名稱 | 功能描述 | 時間復雜度 | 空間復雜度 | 使用場景 |
|---|---|---|---|---|
sort | 對容器元素進行排序（默認升序） | O(n log n) | O(log n) | 適合一般排序，且不關心相等元素順序 |
stable_sort | 保證相等元素的順序不變 | O(n log n) | O(n) | 適合需要穩定排序的場景，如多次排序 |
partial_sort | 僅對前 n 個元素排序 | O(n log k) | O(n) | 只需要排序最小的 n 個元素 |
nth_element | 對第 n 小元素進行排序，且兩側有序 | O(n) | O(1) | 尋找第 n 小元素，適合大數據情況 |
reverse | 反轉容器元素的順序 | O(n) | O(1) | 用于反轉容器，常與排序結合使用 |
（1） sort
- 功能：對容器中的元素進行排序，默認按升序排序。
- 時間復雜度：O(n log n)（平均和最壞情況）。
- 空間復雜度：O(log n)（遞歸調用棧空間）。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = {5, 2, 8, 3, 1};sort(vec.begin(), vec.end());for (int i : vec) {std::cout << i << " "; // 輸出：1 2 3 5 8}cout << endl;system("pause");return 0;
}
注意：
sort是最常用的排序算法，排序速度較快，但不能保證相等元素的順序不變。
（2） stable_sort
- 功能：與
sort相似，但保證相等元素的相對順序不變。 - 時間復雜度：O(n log n)（與
sort相同）。 - 空間復雜度：O(n)（通常需要額外空間用于穩定性保證）。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 5 };stable_sort(vec.begin(), vec.end());for (int i : vec) {cout << i << " "; // 輸出：2 3 5 5 8}cout << endl;system("pause");return 0;
}
注意：
stable_sort適用于需要保留相等元素順序的場景，如按照多個條件排序時。
（3）partial_sort
- 功能：對容器中的前
n個元素進行排序，使它們排好序，其他元素保持原順序。 - 時間復雜度：O(n log k)，其中
n是需要排序的元素數目，k容器中的元素總數。 - 空間復雜度：O(n)。
- 說明：適用于只需要獲取最小（或最大）
n個元素的情況。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 1 };// 排序前3個元素partial_sort(vec.begin(), vec.begin() + 3, vec.end());for (int i : vec) {cout << i << " "; // 輸出：1 2 3 8 5}cout << endl;system("pause");return 0;
}
注意：
partial_sort適用于只需要獲取最小（或最大）n個元素的情況。
（4）nth_element
- 功能：將容器中的元素按照第
n小元素排列，使得第n小元素的左邊小于等于它，右邊大于等于它。 - 時間復雜度：O(n)，即線性時間復雜度。
- 空間復雜度：O(1)。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 1 };// 將第3小的元素放到第3位置，且兩側元素滿足排序條件nth_element(vec.begin(), vec.begin() + 2, vec.end());for (int i : vec) {cout << i << " "; // 輸出：1 2 3 5 8}cout << endl;system("pause");return 0;
}
注意：
nth_element通常用于找到容器中的第n小（或大）元素，不需要完全排序。
（5）reverse
- 功能：反轉容器中元素的順序。
- 時間復雜度：O(n)，
n是容器中的元素數目。 - 空間復雜度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 4, 5 };// 反轉數組reverse(vec.begin(), vec.end());for (int i : vec) {cout << i << " "; // 輸出：5 4 3 2 1}cout << endl;system("pause");return 0;
}
注意：
reverse用于反轉容器中的元素，常用于從降序排序轉換為升序排序。
