C++ std::sort的应用总结

基本用法：

std::sort 是 C++ 标准模板库（STL）中广泛使用的排序函数，用于对数组或容器（如 std::vector）中的元素进行高效排序。以下是关于 std::sort 的详细应用说明，包括其基本用法、不同场景下的应用示例，以及如何处理一些常见问题。

std::sort的核心功能是对序列容器（如数组、std::vector、std::deque）进行升序排序。它接受两个迭代器参数：起始位置和结束位置（结束位置指向最后一个元素之后）。

• 时间复杂度：平均情况O(n \log n)，最坏情况O(n^2)（但实际实现通常优化为O(n \log n)）。
• 稳定性：std::sort不是稳定排序（相等元素的相对顺序可能改变）；如果需要稳定性，使用std::stable_sort。

std::sort 的函数原型如下：

namespace std {template <class RandomIt, class Compare>void sort(RandomIt first, RandomIt last, Compare comp);template <class RandomIt>void sort(RandomIt first, RandomIt last);
}

• first 和 last：需要排序的范围，通常是容器的起始迭代器和结束迭代器，注意这是一个左闭右开的区间 [first, last)。
• comp（可选）：自定义比较规则，默认使用 std::less<T>()，即升序排序。

常见应用场景及示例：

1. 对整数数组进行排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {vector<int> v = {5, 3, 4, 1, 2};sort(v.begin(), v.end());for (const auto& elem : v) {cout << elem << " ";}return 0;
}

输出：1 2 3 4 5

2. 使用自定义比较函数进行降序排序

bool cmp(int a, int b) {return a > b; // 降序
}int main() {vector<int> v = {5, 3, 4, 1, 2};sort(v.begin(), v.end(), cmp);for (const auto& elem : v) {cout << elem << " ";}return 0;
}

或者使用 lambda 表达式：

sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

输出：5 4 3 2 1

3. 对字符串按长度排序

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;int main() {vector<string> v = {"hello", "world", "this", "is", "a", "test"};sort(v.begin(), v.end(), [](const string& s1, const string& s2) {return s1.size() < s2.size(); // 按长度升序});for (const auto& str : v) {cout << str << " ";}return 0;
}

输出：a is this test hello world

4. 对用户定义的类型排序

struct Student {string name;int score;
};bool cmp(const Student& s1, const Student& s2) {return s1.score > s2.score; // 按分数降序排序
}int main() {vector<Student> students = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 95}};sort(students.begin(), students.end(), cmp);for (const auto& student : students) {cout << student.name << " " << student.score << endl;}return 0;
}

输出：

Charlie 95
Alice 90
Bob 85

5. 部分排序

std::sort可以对序列的一部分进行排序，通过指定迭代器范围。此外，C++还提供了std::partial_sort用于只排序前k个元素。

• 部分范围排序：使用std::sort的迭代器参数。
• std::partial_sort：更高效地获取前k个有序元素。

代码示例：部分序列排序

#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> data = {9, 3, 6, 1, 7, 2, 8, 4};// 示例1: 排序前一半元素auto mid = data.begin() + data.size() / 2;  // 中间迭代器std::sort(data.begin(), mid);  // 只排序[begin, mid)// 输出: 前4个元素排序: 1, 3, 6, 9 | 后4个不变: 7,2,8,4std::cout << "Partial sort (first half): ";for (int num : data) {std::cout << num << " ";}std::cout << std::endl;// 示例2: 使用std::partial_sort获取前k小元素std::vector<int> data2 = {5, 2, 9, 1, 5, 6};int k = 3;  // 获取前3小元素std::partial_sort(data2.begin(), data2.begin() + k, data2.end());// 输出: 前3个有序: 1,2,5 | 后3个未定义顺序std::cout << "Top " << k << " elements: ";for (int i = 0; i < k; ++i) {std::cout << data2[i] << " ";}std::cout << std::endl;return 0;
}

6. 使用Lambda表达式（C++11及以上）

在现代C++中，lambda表达式提供了一种简洁的方式来定义匿名比较函数，避免单独声明函数。这使代码更紧凑。

代码示例：使用Lambda进行复杂排序

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>int main() {std::vector<std::string> words = {"apple", "banana", "cherry", "date"};// 示例1: 按字符串长度升序排序std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {return a.size() < b.size();  // 长度短的排在前面});// 输出: date, apple, banana, cherry (长度: 4,5,6,6)std::cout << "Sorted by length: ";for (const auto& word : words) {std::cout << word << " ";}std::cout << std::endl;// 示例2: 多条件排序（先按长度升序，长度相同按字母降序）std::vector<std::string> words2 = {"pear", "kiwi", "apple", "mango"};std::sort(words2.begin(), words2.end(), [](const std::string& a, const std::string& b) {if (a.size() != b.size()) {return a.size() < b.size();  // 长度不同时，长度小的优先}return a > b;  // 长度相同时，按字典序降序});// 输出: kiwi(4), pear(4), apple(5), mango(5) // 解释: pear > kiwi (因为'p' > 'k'), apple < mango (字典序升序但这里用了降序)std::cout << "Multi-criteria sort: ";for (const auto& word : words2) {std::cout << word << " ";}std::cout << std::endl;return 0;
}

处理常见问题：

1. ‌确保容器已包含所需头文件‌：使用 std::sort 前，需要包含 <algorithm> 头文件。
2. ‌正确使用命名空间‌：可以通过 using namespace std; 或在调用时使用 std::sort 来避免命名空间冲突。
3. ‌比较函数的正确性‌：自定义比较函数应确保满足严格弱序关系，否则排序结果可能不正确。
4. ‌处理大型数据集‌：虽然 std::sort 基于快速排序（introsort）+ 插入排序混合实现，效率非常高，但对于极大型数据集，仍需考虑内存和性能问题。

综上所述，std::sort 是 C++ STL 中非常强大的排序工具，适用于各种排序场景。通过合理使用自定义比较函数和 lambda 表达式，可以满足复杂的排序需求。

注意事项和最佳实践

• 性能优化：std::sort在大多数情况下非常高效，但避免在小型序列上使用（如n<10），此时插入排序可能更快。
• 稳定性：如果需要保持相等元素的顺序，改用std::stable_sort。
• 随机访问迭代器：std::sort要求容器支持随机访问（如std::vector、std::array、原生数组）。对于std::list，使用其成员函数list.sort()。
• 异常安全：比较函数不应抛出异常，否则排序行为未定义。
• 时间复杂度分析：
  • 平均情况：$O(n \log n)$，由于快速排序的平均性能。
  • 最坏情况：$O(n^2)$，但现代实现通过混合算法（如introsort）避免此情况。
  • 空间复杂度：$O(\log n)$，用于递归栈。

何时使用：

• 对大型数据集进行通用排序。
• 当自定义排序规则需要灵活性时。
• 在性能关键代码中，优先于手动实现排序算法。