std::sort默认对容器或数组升序排序,采用introsort(快排+堆排+插排),时间复杂度o(n log n),不稳定;要求元素支持
std::sort 默认排序行为是什么
默认情况下,std::sort 对 std::vector 或原生数组升序排列,底层用的是 introsort(快排+堆排+插排混合),平均时间复杂度 O(n log n),不保证稳定。
它要求容器元素支持 运算符重载,比如 <code>int、double、std::string 都可以直用;但自定义结构体不行,除非你显式提供比较逻辑。
用 lambda 写降序或复合条件排序
最常用也最灵活的方式是传一个 lambda 作为第三个参数。注意:lambda 必须返回 bool,且语义是“第一个参数是否应排在第二个参数前面”——不是“是否大于”,而是“是否应该靠前”。
- 降序:
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); - 按绝对值升序:
std::sort(v.begin(), v.end(), [](int a, int b) { return abs(a) - 结构体多级排序(先按
score降序,相等时按name字典升序):std::sort(stus.begin(), stus.end(), [](const auto& x, const auto& y) { return x.score != y.score ? x.score > y.score : x.name < y.name; });
函数对象和函数指针也能用,但有陷阱
你可以写普通函数或仿函数(重载 operator() 的 struct),但要注意生命周期和可调用性: