在 C++ 中，std::sort 是一個非常強大且常用的函數，用于對容器或數組中的元素進行排序。它定義在 <algorithm> 頭文件中。
std::sort 的基本語法
std::sort 的基本語法有以下幾種形式：
-
默認升序排序：
std::sort(first, last);first: 指向要排序范圍的起始元素的迭代器（包含）。last: 指向要排序范圍的結束元素之后一個位置的迭代器（不包含）。- 這種形式會使用元素的默認
<運算符進行比較，實現升序排序。
-
自定義比較規則排序：
std::sort(first, last, comp);first,last: 同上。comp: 一個可調用對象（函數指針、函數對象或 Lambda 表達式），用于定義比較規則。它接受兩個參數，并返回一個bool值。如果第一個參數“小于”第二個參數（即應該排在第二個參數之前），則返回true。
std::sort 的特點
- 頭文件： 必須包含
<algorithm>。 - 迭代器類型： 需要隨機訪問迭代器（RandomAccessIterator）。
std::vector、std::deque、std::string和 C 風格數組都提供隨機訪問迭代器，因此它們可以直接使用std::sort。std::list和std::forward_list不提供隨機訪問迭代器，它們有自己的sort()成員函數。 - 排序算法：
std::sort通常使用 IntroSort（內省式排序），這是一種混合排序算法，結合了快速排序、堆排序和插入排序的優點，以確保在各種情況下的平均和最壞時間復雜度都為 O(N log N)。 - 原地排序：
std::sort是原地排序算法，它直接修改原始容器中的元素，不創建副本。
使用示例
1. 對 std::vector<int> 進行升序排序
#include <iostream>
#include <vector>
#include <algorithm> // 包含 std::sortint main() {std::vector<int> numbers = {5, 2, 8, 1, 9, 4};// 對向量進行升序排序std::sort(numbers.begin(), numbers.end());std::cout << "升序排序后的數字: ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl; // 輸出: 1 2 4 5 8 9return 0;
}
2. 對 std::vector<int> 進行降序排序
方法一：使用 std::greater<T> 函數對象
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // 包含 std::greaterint main() {std::vector<int> numbers = {5, 2, 8, 1, 9, 4};// 對向量進行降序排序std::sort(numbers.begin(), numbers.end(), std::greater<int>());std::cout << "降序排序后的數字: ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl; // 輸出: 9 8 5 4 2 1return 0;
}
方法二：使用 Lambda 表達式
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> numbers = {5, 2, 8, 1, 9, 4};// 使用 Lambda 表達式進行降序排序std::sort(numbers.begin(), numbers.end(), [](int a, int b) {return a > b; // 如果 a 大于 b，則 a 排在 b 之前});std::cout << "降序排序后的數字 (Lambda): ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl; // 輸出: 9 8 5 4 2 1return 0;
}
3. 對 std::string 中的字符進行排序
#include <iostream>
#include <string>
#include <algorithm>int main() {std::string s = "programming";// 對字符串中的字符進行升序排序std::sort(s.begin(), s.end());std::cout << "排序后的字符串: " << s << std::endl; // 輸出: aggimnoprrreturn 0;
}
4. 對自定義結構體或類進行排序 (按特定成員)
假設有一個 Student 結構體，我們想按分數對其進行排序。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>struct Student {std::string name;int score;
};// 自定義比較函數（可作為 Lambda 表達式或獨立函數）
bool compareStudents(const Student& s1, const Student& s2) {return s1.score < s2.score; // 按分數升序排序
}int main() {std::vector<Student> students = {{"Alice", 85},{"Bob", 92},{"Charlie", 78},{"David", 92} // Bob 和 David 分數相同};// 使用自定義比較函數對學生進行排序std::sort(students.begin(), students.end(), compareStudents);std::cout << "按分數排序后的學生: " << std::endl;for (const Student& s : students) {std::cout << s.name << ": " << s.score << std::endl;}/* 輸出:Charlie: 78Alice: 85Bob: 92David: 92*/// 假設分數相同，按名字字母順序排序std::sort(students.begin(), students.end(), [](const Student& s1, const Student& s2) {if (s1.score != s2.score) {return s1.score < s2.score; // 分數不同時按分數排序}return s1.name < s2.name; // 分數相同時按名字排序});std::cout << "\n按分數然后按名字排序后的學生: " << std::endl;for (const Student& s : students) {std::cout << s.name << ": " << s.score << std::endl;}/* 輸出:Charlie: 78Alice: 85Bob: 92David: 92 (注意：這里Bob和David的相對順序可能不變，因為它們在原始數據中是Bob在前。如果想確保 David 在 Bob 之后，比較器應返回 true 只有當 s1 嚴格小于 s2。當前輸出是正確的，因為 Bob 92, David 92, Bob 的 'B' < David 的 'D'。實際輸出取決于 `std::sort` 的穩定性，但 `std::sort` 通常是不穩定的，對于相等元素，相對順序可能改變。如果需要穩定性，使用 `std::stable_sort`。但在這個例子中，因為Bob和David名字不同，所以會進一步排序。*/return 0;
}
總結
std::sort 是 C++ 中進行排序的首選工具，因為它高效、靈活，并且易于使用。通過提供自定義比較規則，你可以根據幾乎任何條件對各種數據類型進行排序。
--鏈表01)
