函数原型与用法
sort函数通常接受两个或三个参数：前两个参数定义了要排序的元素的范围（begin迭代器和end迭代器），第三个参数（可选）则是一个比较函数，用于自定义排序规则。如果没有提供比较函数，则默认使用小于运算符（<）进行升序排序。以下是基本的函数原型：
template <class RandomIt>
void sort(RandomIt first, RandomIt last);
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
使用示例：
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> numbers = {5, 2, 8, 1, 9, 4};
std::sort(numbers.begin(), numbers.end()); // 升序排序
for (int number : numbers) {
std::cout << number << " ";
}
std::cout << std::endl; // 输出：1 2 4 5 8 9
// 降序排序 (使用lambda表达式)
std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; });
for (int number : numbers) {
std::cout << number << " ";
}
std::cout << std::endl; // 输出：9 8 5 4 2 1
return 0;
}
算法复杂度
sort函数通常使用高效的排序算法，例如快速排序，因此其平均时间复杂度为O(n log n)，其中n是要排序的元素的数量。在最坏情况下，快速排序的时间复杂度可能达到O(n^2)，但STL的实现通常会采取优化措施以避免这种情况。sort函数的空间复杂度通常为O(log n)，用于递归栈的深度。
自定义排序
sort函数允许使用自定义比较函数，这使得可以根据特定的需求对数据进行排序。比较函数需要接受两个参数，并返回一个布尔值，用于指示这两个元素的相对顺序。例如，可以编写一个比较函数来按学生的年龄或成绩进行排序。
使用自定义比较函数的例子：
#include <algorithm>
#include <vector>
#include <iostream>
struct Student {
std::string name;
int age;
};
bool compareStudents(const Student& a, const Student& b) {
return a.age < b.age; // 按年龄升序排序
}
int main() {
std::vector<Student> students = {
{"Alice", 20},
{"Bob", 22},
{"Charlie", 19}
};
std::sort(students.begin(), students.end(), compareStudents);
for (const auto& student : students) {
std::cout << student.name << ": " << student.age << std::endl;
}
// 输出: Charlie: 19, Alice: 20, Bob: 22
return 0;
}
注意事项
在使用sort函数时，需要确保所排序的范围是有效的，并且元素支持小于运算符（或者提供了自定义的比较函数）。sort函数不保证排序的稳定性，即相等元素的相对顺序可能在排序后发生改变。如果需要保持稳定性，可以使用stable_sort函数。
结论
C++标准库中的sort函数是一个强大而灵活的工具，用于对各种数据结构进行排序。它提供了高效的性能和方便的接口，支持升序、降序以及自定义排序规则。正确使用sort函数可以极大地简化代码，并提高程序的效率。