升序排序使用std::sort默认行为，降序需传入std::greater()；自定义排序可使用函数指针或Lambda表达式；std::sort平均和最坏时间复杂度均为O(n log n)，适用于大多数场景，但小数据量、近有序序列或需稳定排序时可考虑插入排序或std::stable_sort。
C++ 中对 vector 排序，通常使用 std::sort 函数，可以自定义比较函数来实现更灵活的排序规则。
使用 std::sort 函数对 vector 进行排序。
如何使用 std::sort 函数对 vector 进行升序和降序排序？
std::sort 函数是 C++ 标准库 运算符进行升序排序。
升序排序：
立即学习“C++免费学习笔记（深入）”；
#include#include #include int main() { std::vector 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; return 0; }
降序排序：
要进行降序排序，可以使用 std::greater 仿函数作为比较函数。
#include#include #include int main() { std::vector numbers = {5, 2, 8, 1, 9, 4}; std::sort(numbers.begin(), numbers.end(), std::greater ()); // 降序 std::cout << "降序排序后: "; for (int num : numbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }
在这个例子中，std::greater 创建了一个比较函数对象，它定义了 > 运算符的行为，从而实现了降序排序。
如何自定义比较函数对 vector 进行排序？
有时，默认的升序或降序排序无法满足需求。例如，需要按照元素的某个特定属性进行排序，或者需要自定义排序规则。这时，可以自定义比较函数。
使用函数指针：
#include#include #include struct Person { std::string name; int age; }; bool compareByAge(const Person& a, const Person& b) { return a.age < b.age; // 按年龄升序 } int main() { std::vector people = { {"Alice", 30}, {"Bob", 25}, {"Charlie", 35} }; std::sort(people.begin(), people.end(), compareByAge); std::cout << "按年龄排序后: " << std::endl; for (const auto& person : people) { std::cout << person.name << ": " << person.age << std::endl; } return 0; }
使用 Lambda 表达式：
Lambda 表达式提供了一种更简洁的方式来定义比较函数。
#include#include #include struct Person { std::string name; int age; }; int main() { std::vector people = { {"Alice", 30}, {"Bob", 25}, {"Charlie", 35} }; std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) { return a.name < b.name; // 按姓名升序 }); std::cout << "按姓名排序后: " << std::endl; for (const auto& person : people) { std::cout << person.name << ": " << person.age << std::endl; } return 0; }
Lambda 表达式 [](const Person& a, const Person& b) { return a.name 定义了一个匿名函数，它接受两个 Person 对象作为参数，并返回一个布尔值，指示它们的姓名是否应该交换位置。
性能优化：std::sort 的时间复杂度是多少？在哪些情况下应该考虑使用其他排序算法？
std::sort 通常使用 IntroSort 算法，这是一种混合排序算法，结合了快速排序、堆排序和插入排序的优点。平均时间复杂度为 O(n log n)，最坏情况下的时间复杂度也是 O(n log n)。
何时考虑其他排序算法：
-
数据量非常小： 对于非常小的
vector，插入排序可能更快，因为它具有较低的常数因子。 -
数据基本有序： 如果
vector已经接近有序，插入排序或冒泡排序可能更有效。 -
需要稳定排序：
std::sort不是稳定排序算法，这意味着相等元素的相对顺序可能会改变。如果需要保持相等元素的原始顺序，可以考虑使用std::stable_sort，但它的性能可能略低于std::sort。 - 特定数据类型： 对于某些特定数据类型，例如整数，计数排序或基数排序可能更有效，但这些算法通常需要额外的内存空间。
示例：使用 std::stable_sort：
#include#include #include struct Item { int value; int index; // 记录原始索引 }; bool compareByValue(const Item& a, const Item& b) { return a.value < b.value; } int main() { std::vector - items = { {5, 0}, {2, 1}, {5, 2}, // 与第一个 5 值相等 {1, 3} }; std::stable_sort(items.begin(), items.end(), compareByValue); std::cout << "稳定排序后: " << std::endl; for (const auto& item : items) { std::cout << "Value: " << item.value << ", Index: " << item.index << std::endl; } return 0; }
在这个例子中，即使有两个 Item 对象的 value 相同（都为 5），它们在排序后的 vector 中的相对顺序仍然保持不变，即原始索引为 0 的 Item 在原始索引为 2 的 Item 之前。
