sort 排序

读完能做什么

• 能用 sort(v.begin(), v.end()) 把一组数据从小到大排好，并说出排完之后每个位置是什么。
• 能用 greater<int>() 改成从大到小，也能只排区间里的一段位置。
• 能写一个自己的比较规则，实现“先按成绩、再按姓名”这类多关键字排序。
• 能说清 stable_sort 保证“相等的元素保持原来的先后顺序”，而 sort 不做这个保证。

为什么需要它

一张成绩表常常需要按分数排好再处理：

手工排序要写两层循环、反复交换相邻元素，代码长还容易写错。更麻烦的是，题目里的排序要求经常在变：有时要升序，有时要降序，有时要先按成绩、成绩相同再按姓名。每次都手写一遍排序并不划算。

这类“把一段数据按某个规则重新排列”的动作在程序里出现得太多，标准库把它做成了一个函数，就是 sort。它处理的对象是“从哪个位置到哪个位置”的一段数据，规则由你给，也可以不给。

它是什么

一句话：sort(first, last) 把区间 [first, last) 里的元素按规则重新排列，默认从小到大。

几个必须就地看懂的概念：

区间 [first, last)。 迭代器是“指向容器中某个位置的游标”。v.begin() 指向第一个元素，v.end() 指向最后一个元素后面一个位置（尾后位置）。两个位置组成一个左闭右开区间：包含 first 指向的元素，不包含 last 指向的元素。所以 [v.begin(), v.end()) 正好是整个 vector。区间这套约定在 容器、迭代器与区间 里有系统讲解。

默认规则是 <。 不给第三个参数时，sort 用 < 判断“谁应该排在前面”：如果 a < b，就把 a 排在 b 前面，于是结果从小到大。

比较器：自己定“谁排在前面”。 第三个参数 comp 是一个判断规则：comp(a, b) 返回 true 表示 a 应该排在 b 前面。它可以是普通函数，也可以是函数对象（带 operator() 的结构体）。greater<int>() 就是标准库给的一个现成规则，含义正好和 < 相反，所以它能排出降序。比较规则的写法见 比较规则与函数对象。

随机访问迭代器。 sort 要求迭代器能随意跳转、能相减。vector、deque、string、普通数组都满足；list 的迭代器只能 ++ / --，不满足，所以 list 要用成员函数 l.sort()。

它会修改数据。 sort 没有返回值，它直接改动区间里元素的顺序，不需要你把结果接住。

适用场景：数据可以重新排列、你要的是有序结果。使用时要 #include <algorithm>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

用数据 [4, 1, 3, 1] 演示默认排序：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 1, 3, 1};

    sort(v.begin(), v.end());          // 默认按从小到大排序

    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

1 1 3 4 

逐行看：

• vector<int> v = {4, 1, 3, 1}; 四个元素，下标依次是 0、1、2、3。
• sort(v.begin(), v.end()) 处理整个 vector。v.begin() 指向第一个 4，v.end() 是最后一个元素后面那个位置，区间正好覆盖 4 个元素。
• 排序后从小到大是 1 1 3 4，两个 1 并排。sort 直接改动了 v，循环按顺序打印就得到这一行。
• 输出末尾有一个空格，是因为循环每次都打印“数字 + 空格”。这不影响结果，只是打印格式。

一步步看变化

还是这组数据 [4, 1, 3, 1]，依次做三次排序：先只排前两个位置，再排全体升序，最后排全体降序。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 1, 3, 1};

    sort(v.begin(), v.begin() + 2);            // 只排前两个位置
    cout << "只排前两个位置后：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    sort(v.begin(), v.end());                  // 全体升序
    cout << "全体升序后：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    sort(v.begin(), v.end(), greater<int>());  // 全体降序
    cout << "全体降序后：";
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

只排前两个位置后：1 4 3 1 
全体升序后：1 1 3 4 
全体降序后：4 3 1 1 

• 第 1 步：区间是 [v.begin(), v.begin() + 2)，只覆盖下标 0、1 上的 4、1，排成 1、4；下标 2、3 的 3、1 没被碰，保持原样，得到 1 4 3 1。
• 第 2 步：[v.begin(), v.end()) 覆盖全部，排成 1 1 3 4。
• 第 3 步：greater<int>() 让大的排在前面，排成 4 3 1 1。

区间是左闭右开的，终点取不到。所以“只排前两个位置”要写 v.begin() + 2 而不是 v.begin() + 1。

逐项扩展核心操作

降序：greater<int>()

把第三个参数换成 greater<int>()，规则就变成“大的在前”：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 1, 3, 1};

    sort(v.begin(), v.end(), greater<int>());

    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

4 3 1 1 

greater<int>() 是一个函数对象：它带一个 operator()，greater<int>()(a, b) 判断 a > b。把它交给 sort，sort 就用 > 来决定先后，于是得到降序。

按自己的规则排序（多关键字）

数据换成带姓名和成绩的学生。要求“成绩高的在前，成绩相同则姓名小的在前”：

#include <bits/stdc++.h>
using namespace std;

struct Student {
    string name;
    int score;
};

// 规则：成绩高的排前面；成绩相同则姓名小的排前面
bool byScoreDescThenName(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
}

int main() {
    vector<Student> s = {{"A", 90}, {"B", 80}, {"C", 90}};

    sort(s.begin(), s.end(), byScoreDescThenName);

    for (const Student& x : s) cout << x.name << ' ' << x.score << '\n';
    return 0;
}

输出：

A 90
C 90
B 80

规则分两段读：

• if (a.score != b.score) return a.score > b.score;：成绩不同时，用 > 让成绩高的排前面。
• return a.name < b.name;：只有成绩相同时才会走到这一句，用 < 让姓名小的排前面。

A 和 C 都是 90 分，进入第二段比较，"A" < "C" 为真，所以 A 排在 C 前面；B 只有 80 分，排在最后。

比较器必须满足严格弱序。 “严格弱序”是一组关于比较规则的约定，实际写作时记住两条：comp(x, x) 必须返回假（自己不能排在自己前面），以及“相等”的元素互相比较都必须返回假。所以判断用 <（或 >），不能用 <=：comp(x, x) 会返回真，排序行为就没有保证。多关键字时也要让每条分支单独满足这两条。

stable_sort：相等元素保持原顺序

看这组数据，A 和 C 的成绩相同：

#include <bits/stdc++.h>
using namespace std;

struct Student {
    string name;
    int score;
};

// 只比较成绩，不比较姓名
bool byScoreAsc(const Student& a, const Student& b) {
    return a.score < b.score;
}

int main() {
    vector<Student> s = {{"A", 90}, {"B", 80}, {"C", 90}};

    // 稳定排序：成绩相同的学生保持原来的先后顺序
    stable_sort(s.begin(), s.end(), byScoreAsc);

    for (const Student& x : s) cout << x.name << ' ' << x.score << '\n';
    return 0;
}

输出：

B 80
A 90
C 90

比较规则只看成绩，A 和 C 在它眼里“相等”。stable_sort 保证相等元素保持排序前的相对顺序：原来 A 在 C 前面，排完后 A 仍在 C 前面。加上 B，结果就是 B、A、C。

sort 不做这个保证。 标准没有规定 sort 会把相等的元素排成什么顺序，换一个编译器、换一组数据都可能不同。所以：

• 需要“同分保持原顺序”时，用 stable_sort，不要指望 sort。
• 不要写“用 sort 排完后同分的次序是……”这类结论，因为标准根本没规定它。
• 如果只关心成绩、不在意同分者的先后，用 sort 就够了，而且通常更快。

关于 sort 和 unique 的配合：先用 sort 把相等的值聚到一起，再用 unique 合并相邻相等元素、erase 真正删除，就能实现“全体去重”。这个组合的说法见 unique 去重。

什么时候选它、哪里容易错

区间是左闭右开的。 sort(v.begin(), v.end()) 排全体；sort(v.begin() + 1, v.end()) 只排下标 1 到末尾。终点写多一格、少一格，参与排序的元素就变了。

默认升序，降序要显式给规则。 sort(v.begin(), v.end()) 是从小到大；要降序得写 sort(v.begin(), v.end(), greater<int>())。

比较器不能用 <=。 用 <= 时 comp(x, x) 会返回真，违反严格弱序，排序结果不可靠，某些编译器甚至会越界访问：

// 错误示例：比较器写成 a <= b 违反了严格弱序，结果不可靠
#include <bits/stdc++.h>
using namespace std;

bool lessOrEqual(int a, int b) {
    return a <= b;                          // 相等时返回真，违反严格弱序
}

int main() {
    vector<int> v = {4, 1, 3, 1};

    sort(v.begin(), v.end(), lessOrEqual);  // 错误：相等元素互相比较时返回真
    return 0;
}

这段能编译，但 a <= b 让相等元素互相比较时返回真，破坏了排序算法的前提，运行结果没有保证。本页不给它写运行结果。正确写法是 a < b。

sort 需要随机访问迭代器。 list 的迭代器只能逐个前进，sort(l.begin(), l.end()) 编译不过，要用成员函数 l.sort()（见 list 链表）。

排序会打乱原来的位置。 排完之后元素的下标全变了，之前记下的迭代器或下标不再对应原来的元素。要按“原来的第几个”访问数据，得先另存一份。

复杂度。 sort 是 O(n log n)。stable_sort 也保证 O(n log n) 的比较次数，但为了保持稳定，通常需要额外空间，实现代价比 sort 高，所以没有特殊需要时优先用 sort。

选读。 sort 内部混合了快速排序、插入排序和堆排序（叫“内省式排序”），在递归太深时切换到堆排序避免退化。这些是实现细节，不影响你怎么调用它，也不保证任何“相等元素的顺序”。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

vector<int> v = {3, 1, 2, 1};
sort(v.begin(), v.end(), greater<int>());
for (int x : v) cout << x << ' ';

第 2 题：修改代码

下面这段片段把 [4, 1, 3, 1] 从小到大排序，请把它改成从大到小，让输出变成 4 3 1 1：

vector<int> v = {4, 1, 3, 1};
sort(v.begin(), v.end());          // 改成降序
for (int x : v) cout << x << ' ';

验证条件：先说出改完之后第一个元素是几，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {3, 1, 2, 1};
    sort(v.begin(), v.end(), greater<int>());
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

3 2 1 1 

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 1, 3, 1};
    sort(v.begin(), v.end(), greater<int>());
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

4 3 1 1 

立即练习

两道题都只需要数组、循环和本页讲过的排序操作。做完后请说明：第二题里“同生日的人输入靠后先输出”这条要求，你把它写在了规则的哪一句？如果题目改成“同生日保持输入顺序”，用 stable_sort 只比生日能不能做到？为什么？