C / C++ / 系统课时
用 sort 排序基础类型数据
用 sort 排序基础类型数据
std::sort 适合把 vector、数组等随机访问区间快速排成指定顺序。本节用一个完整程序演示升序与降序排序,并重点说明半开区间、默认比较规则以及最容易写错的边界。
学习目标
- 能使用
std::sort对基础类型区间进行升序和降序排序。 - 理解
[first, last)半开区间以及默认按小于关系比较的规则。 - 能判断哪些容器可以直接使用
std::sort,并识别常见边界错误。
sort 对什么区间工作
std::sort(first, last) 排序的是 [first, last):包含 first 指向的元素,不包含 last。它要求迭代器支持随机访问,因此 vector、array、deque 以及原生数组可以使用;list 的迭代器不满足要求,应使用成员函数 list::sort()。
没有提供比较器时,std::sort 使用默认的小于关系确定次序。对 int、double 等基础类型,这通常就是数值升序。
完成一次升序与降序排序
下面的程序先对整数升序排序,再通过 std::greater<int> 改为降序。第二次排序仍然操作同一个 [begin, end) 区间。
cpp
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
void print(const std::vector<int>& values) {
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
}
int main() {
std::vector<int> values{7, 2, 9, 2, 5};
// 未提供比较器时按升序排列。
std::sort(values.begin(), values.end());
print(values);
// std::greater<int> 让较大的元素排在前面。
std::sort(values.begin(), values.end(), std::greater<int>{});
print(values);
}预期输出
text
2 2 5 7 9
9 7 5 2 2std::sort 会原地重排元素,不会创建一个新的已排序容器。若原顺序仍有用途,应先复制数据再排序。对于等价元素,std::sort 不保证保留它们原来的相对顺序;需要稳定排序时应选择 std::stable_sort。
区间边界决定谁会被排序
排序子区间时,仍然遵守“左闭右开”。例如只想排序下标 [1, 4),可以写 std::sort(values.begin() + 1, values.begin() + 4),下标 4 对应的元素不会参与排序。
std::sort 的比较次数复杂度为 。处理普通内存容器中的可随机访问数据时,它通常是默认排序工具;若容器本身不提供随机访问迭代器,则应优先使用该容器提供的排序能力。
按自己的节奏,确认真正理解。