C++ sort排序函数用法详解

前言

std::sort定义在<algorithm>中，是 C++ 最常用的排序算法。它的接口只有两个核心参数——首迭代器和尾后迭代器——再加一个可选的比较器。看似简单，但围绕它有大量误用：比较器写成<=、对std::list调用、以为排序稳定、在比较器里修改元素。这些错误有的直接编译失败，有的则是未定义行为（undefined behavior, UB），运行时才以奇怪的方式暴露。

先把几个事实说清楚。std::sort要求随机访问迭代器，因此std::vector、std::array、普通数组、std::deque可以用，std::list、std::forward_list不行（它们有成员函数sort）。它不保证稳定，需要稳定排序用std::stable_sort。它的比较次数是 O(N log N)，但具体实现（内省排序、混合算法）由标准库决定，标准不规定。比较器必须满足严格弱序（strict weak ordering），违反它是 UB，不是“结果可能不理想”。

本文覆盖基本用法、自定义比较器、结构体多关键字排序、稳定性与部分排序，并给出常见错误的正确写法。示例以 C++17 为基准。

一、基本用法

最简单的形式是对一个区间升序排序：

// 适用于 C++17
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

int main()
{
std::vector<int> v{5, 2, 9, 1, 5, 6};
std::sort(v.begin(), v.end()); // 升序

std::array<int, 4> a{4, 3, 2, 1};
std::sort(a.begin(), a.end()); // 对 std::array 同样适用

int raw[5] = {5, 4, 3, 2, 1};
std::sort(raw, raw + 5); // 普通数组用指针作为迭代器

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

first与last构成左闭右开区间[first, last)，last是尾后位置，不参与排序。对空区间或只有一个元素的区间调用sort是合法的，什么也不做。

降序有两种常见写法：

// 适用于 C++17
#include <algorithm>
#include <functional>
#include <vector>

void sort_desc(std::vector<int>& v)
{
std::sort(v.begin(), v.end(), std::greater<int>{});
// 或：std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
}

std::greater<int>在<functional>中。C++14 起可以写std::greater<>{}，让模板实参由调用时推导，省去重复写类型。

二、比较器的语义

比较器comp(a, b)返回true表示“a 应该排在 b 前面”。它必须满足严格弱序，可以概括为四条：

1. 
   
2. 对任意 a，comp(a, a)为false（非自反）；
3. 
   
4. 若comp(a, b)为真，则comp(b, a)为假（非对称）；
5. 
   
6. 若comp(a, b)且comp(b, c)，则comp(a, c)（传递）；
7. 
   
8. 不可比较的元素之间满足传递性（等价关系传递）。
9. 
   

写成a <= b违反第 1 条：comp(a, a)会返回true。标准库的排序实现依赖“小于”语义做划分和二分，<=会让它把相等元素来回搬运，甚至越界访问。这是 UB，不是“排序结果不稳定”这么轻。

// 适用于 C++17
#include <algorithm>
#include <vector>

void wrong(std::vector<int>& v)
{
std::sort(v.begin(), v.end(),
[](int a, int b) { return a <= b; }); // UB
}

void right(std::vector<int>& v)
{
std::sort(v.begin(), v.end(),
[](int a, int b) { return a < b; }); // 严格弱序
}

比较器还应当是纯函数：不修改被比较的元素，不依赖会在排序过程中变化的外部状态。如果比较器读取一个全局计数器并在内部自增，排序过程中元素间的相对顺序会随调用次序改变，同样破坏严格弱序。

三、结构体与多关键字排序

对结构体排序，比较器要明确“主键、次键”：

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

struct Person {
std::string name;
int age;
double score;
};

int main()
{
std::vector<Person> people{
{"Ann", 30, 88.5},
{"Bob", 25, 92.0},
{"Cid", 30, 75.0},
{"Dan", 25, 92.0}
};

// 按年龄升序，年龄相同按分数降序，再按姓名升序
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
if (a.age != b.age) {
return a.age < b.age;
}
if (a.score != b.score) {
return a.score > b.score;
}
return a.name < b.name;
});

// 等价的简洁写法：std::tie 构造可比较的元组
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
return std::tie(a.age, b.name) < std::tie(b.age, b.name);
});

for (const auto& p : people) {
std::cout << p.name << ' ' << p.age << '\n';
}
return 0;
}

std::tie生成左值引用组成的tuple，tuple的比较是按元素字典序进行的，因此std::tie(a.age, a.name) < std::tie(b.age, b.name)等价于“先比年龄，再比姓名”。注意不能把“降序字段”和“升序字段”混在一个tie里，因为tuple的每个元素都按同一种方向比较；混合方向时还是手写分支更清楚。

如果结构体本身定义了operator<，可以直接调用无比较器版本：

// 适用于 C++17
struct Point {
int x;
int y;
};

bool operator<(const Point& a, const Point& b)
{
return a.x != b.x ? a.x < b.x : a.y < b.y;
}

四、稳定性、部分排序与容器选择

稳定性

std::sort不保证相等元素的相对顺序。如果业务要求“先按分数排，再按姓名排，且同分者保持原有顺序”，应使用std::stable_sort：

// 适用于 C++17
#include <algorithm>
#include <string>
#include <vector>

struct Record {
std::string name;
int score;
};

void sort_stable(std::vector<Record>& v)
{
std::stable_sort(v.begin(), v.end(),
[](const Record& a, const Record& b) {
return a.score > b.score;
});
}

stable_sort的比较次数同样是 O(N log N)，但可能需要额外的临时存储；具体实现和内存用量由标准库决定，标准不规定。

部分排序

只需要前 K 个元素有序时，不必对整个区间排序：

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <vector>

void top_k(std::vector<int>& v, std::size_t k)
{
if (k < v.size()) {
std::partial_sort(v.begin(), v.begin() + static_cast<std::ptrdiff_t>(k), v.end());
}
}

partial_sort(first, middle, last)之后，[first, middle)是整体最小的 K 个元素且已排序，[middle, last)的顺序未指定。如果只关心“第 K 小是谁”而不关心前面是否有序，用std::nth_element，平均复杂度是线性的。

容器选择

对std::list调用std::sort会在编译期报错，因为它的迭代器不满足随机访问要求。std::list::sort是成员函数，稳定，复杂度 O(N log N)，并且只重新链接节点，不移动元素。

常见坑点

1. 
   
2. ❌ 比较器写return a <= b;。
3. 
   

✅ 必须是严格弱序，用a < b；<=会让comp(a, a)为真，属于 UB。

1. 
   
2. ❌ 比较器依赖并在内部修改外部状态。
3. 
   

✅ 比较器应是纯函数；需要附加信息就作为参数传入，不要在比较过程中改变它。

1. 
   
2. ❌ 对std::list或std::forward_list调用std::sort。
3. 
   

✅ 用它们的成员sort()；std::sort要求随机访问迭代器。

1. 
   
2. ❌ 认为std::sort稳定，依赖相等元素的原有顺序。
3. 
   

✅ 需要稳定用std::stable_sort；std::sort只保证有序，不保证相等元素的相对次序。

1. 
   
2. ❌ 在比较器里用a.score - b.score的符号做判断，整数相减可能溢出。
3. 
   

✅ 写成a.score < b.score或a.score > b.score，不要用减法制造溢出风险。

1. 
   
2. ❌ 对含 NaN 的浮点数组直接用<排序。
3. 
   

✅ NaN 与任何值比较都为假，破坏严格弱序。先把 NaN 过滤或定义明确的排序规则。

1. 
   
2. ❌ 排序后继续使用指向原元素的迭代器，以为它还指向原来的值。
3. 
   

✅std::sort会重排元素；迭代器本身仍有效（对vector不重新分配），但指向的位置内容已变。

1. 
   
2. ❌ 只对前 K 个元素排序却调用了完整的std::sort。
3. 
   

✅ 用std::partial_sort或std::nth_element，避免做多余的工作。

总结

std::sort的难点不在调用，而在比较器：只要保证它满足严格弱序、不修改元素、不依赖变化的状态，剩下的交给标准库即可。需要稳定就用stable_sort，需要部分有序就用partial_sort，不要把不同需求都压给同一个函数。