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 2

std::sort 会原地重排元素,不会创建一个新的已排序容器。若原顺序仍有用途,应先复制数据再排序。对于等价元素,std::sort 不保证保留它们原来的相对顺序;需要稳定排序时应选择 std::stable_sort。

区间边界决定谁会被排序

排序子区间时,仍然遵守“左闭右开”。例如只想排序下标 [1, 4),可以写 std::sort(values.begin() + 1, values.begin() + 4),下标 4 对应的元素不会参与排序。

std::sort 的比较次数复杂度为 O(nlog⁡n)O(n \log n)。处理普通内存容器中的可随机访问数据时,它通常是默认排序工具;若容器本身不提供随机访问迭代器,则应优先使用该容器提供的排序能力。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 sort 排序基础类型数据

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通