前言

std::sort是 C++ 标准库最常用的算法之一，声明在<algorithm>里，作用是把一个区间按升序或自定义规则重新排列。它接受一对随机访问迭代器，默认用operator<比较元素，也可以传入自定义比较器。日常代码里排序std::vector、内置数组、std::string的字符，几乎都用它。

关于它有两个流传很广的误解。第一个是「std::sort是稳定排序」——并不是。元素相等时它们的相对次序不保证保持，需要稳定就改用std::stable_sort。第二个是「比较器随便写，只要大小关系差不多就行」——比较器必须满足严格弱序（strict weak ordering），写成<=或>=在标准层面是未定义行为（undefined behavior, UB），在某些实现上会直接越界访问。

本文先讲std::sort的接口与复杂度保证，再说明比较器的数学要求，然后按使用场景给出示例：普通升序降序、结构体多关键字排序、只需要前若干名、只需要中位数、以及对链表排序。最后列出实际写代码时最常见的错误。

一、接口与复杂度

标准给出的两个重载是：

两个版本都返回void，排序是原地进行的。要求[first, last)是有效区间，迭代器至少是随机访问迭代器（random access iterator），元素可交换（swappable），比较器对元素类型构成严格弱序。

复杂度方面，C++11 起标准要求std::sort至多进行 O(N log N) 次比较，其中 N 是区间长度。C++11 之前只写了「平均约 N log N」，没有最坏情况的硬性上界。这一点常被忽略：今天的标准库实现通常能保证最坏 O(N log N)，是因为普遍采用内省排序（introsort），而不是标准规定了某一种算法。

内省排序的思路是：以快速排序为主体，用递归深度作监控，深度超过约 2×log₂N 时切换成堆排序，避免快排退化成 O(N²)；小区间（常见阈值是十几个元素）改用插入排序，减少函数调用和递归开销。需要强调，这只是主流实现的做法，标准并未规定必须如此，具体阈值和行为属于实现细节，不能写进可移植代码的假设里。

另外，std::sort不分配额外内存（实现可能用少量栈空间），而std::stable_sort在额外内存不足时可能退化为 O(N log²N) 次比较。这也是「默认用 sort，需要稳定才用 stable_sort」的原因之一。

二、比较器为什么必须满足严格弱序

设比较器为comp，严格弱序要求对区间内任意元素 a、b、c 满足：

1. 
   
2. 非自反：comp(a, a)必须为假。
3. 
   
4. 非对称：若comp(a, b)为真，则comp(b, a)必须为假。
5. 
   
6. 传递：若comp(a, b)与comp(b, c)都为真，则comp(a, c)为真。
7. 
   
8. 等价关系传递：若 a 与 b 等价（互相都不小于对方），b 与 c 等价，则 a 与 c 等价。
9. 
   

a <= b违反第一条：comp(a, a)为真。排序算法内部会据此认为元素小于自己，划分区间时可能把下标推到边界之外。这种错误不一定立刻崩溃，可能只是结果乱序，也可能在某个数据规模上越界，所以特别难查。

正确的写法是只用<表达「严格小于」，相等时返回false。多关键字排序时，把「相等」的分支交给下一个关键字，最后一个关键字仍然用严格小于：

// 适用于 C++17
bool lessByAgeThenName(const Employee& a, const Employee& b) {
if (a.age != b.age) {
return a.age < b.age;
}
return a.name < b.name; // 相等时返回 false，符合严格弱序
}

用std::tie可以把多关键字比较写得紧凑，它按成员声明顺序生成一个引用元组，元组的operator<是逐元素字典序：

// 适用于 C++17
bool lessByAgeThenName(const Employee& a, const Employee& b) {
return std::tie(a.age, a.name) < std::tie(b.age, b.name);
}

std::tie返回的是引用元组，比较时不会拷贝字符串，前提是被比较的成员在比较期间不被修改。比较器本身也不应该修改元素——标准要求谓词不能通过参数施加副作用，否则行为未定义。

三、典型使用场景

场景一：基本类型升序与降序

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

void basicSort(std::vector<int>& v) {
std::sort(v.begin(), v.end()); // 升序，用 operator<
std::sort(v.begin(), v.end(), std::greater<int>()); // 降序
}

std::greater<int>声明在<functional>里。用std::greater<>（C++14 起的透明比较器）可以省掉模板实参，让编译器推导：

// 适用于 C++14 及以上
std::sort(v.begin(), v.end(), std::greater<>());

场景二：结构体按多个字段排序

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

struct Employee {
std::string name;
int age = 0;
double salary = 0.0;
};

void sortStaff(std::vector<Employee>& staff) {
std::sort(staff.begin(), staff.end(),
[](const Employee& a, const Employee& b) {
if (a.salary != b.salary) {
return a.salary > b.salary; // 工资从高到低
}
return std::tie(a.age, a.name) < std::tie(b.age, b.name);
});
}

这里第一关键字是降序（用>），后面两个是升序（用<），混用没有问题，只要每个分支都表达严格序。浮点数比较要注意：如果数据里可能有 NaN，a.salary != b.salary与<的组合不再构成严格弱序，因为 NaN 与任何值（包括自己）都不相等也不小于。含 NaN 的数据应先清洗，或者用std::isnan显式定义 NaN 的排序位置。

场景三：只要前 k 名

对整个区间排序是 O(N log N)，如果只关心最小的 k 个，std::partial_sort更合适：

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

std::vector<int> topK(std::vector<int> v, std::size_t k) {
if (k > v.size()) {
k = v.size();
}
std::partial_sort(v.begin(), v.begin() + static_cast<std::ptrdiff_t>(k), v.end());
v.resize(k);
return v;
}

partial_sort(first, middle, last)保证[first, middle)是整体中最小的若干元素且已排好序，其余元素的顺序未指定。复杂度约 O(N log k)。

场景四：只要中位数或第 k 小

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

int median(std::vector<int> v) {
const std::size_t mid = v.size() / 2;
std::nth_element(v.begin(), v.begin() + static_cast<std::ptrdiff_t>(mid), v.end());
return v[mid];
}

std::nth_element平均 O(N)，保证位置mid上的元素就是「如果整体排序后该位置应有的元素」，并且它左边的都不大于它、右边的都不小于它，但两侧内部无序。调用前要确保容器非空。

场景五：链表排序

std::sort需要随机访问迭代器，std::list的迭代器是双向的，直接传进去编译不过。链表应用成员函数sort：

// 适用于 C++17
#include <list>

void sortList(std::list<int>& lst) {
lst.sort(); // 升序
lst.sort(std::greater<int>()); // 降序
}

std::list::sort是稳定排序，且不要求元素可随机访问，通常用归并实现。std::forward_list也有成员sort。

场景六：稳定排序

当相等元素的原始次序有业务含义时，用std::stable_sort：

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

void stableByScore(std::vector<Employee>& staff) {
std::stable_sort(staff.begin(), staff.end(),
[](const Employee& a, const Employee& b) {
return a.salary > b.salary;
});
}

如果先按姓名排过一遍，再按工资稳定排序，工资相同的员工之间仍保持姓名的次序，这就是稳定排序的用途。

四、几个容易混淆的边界

std::sort不会改变元素的个数，也不会让迭代器失效（元素被移动，但容器本身不重新分配）。不过，如果比较器捕获了外部状态并在排序过程中修改它，或者比较器依赖的元素在排序过程中被其他线程修改，行为都是未定义的。

对内置数组也可以直接用：

// 适用于 C++17
int a[] = {3, 1, 4, 1, 5};
std::sort(std::begin(a), std::end(a));

std::begin/std::end在<iterator>里，对数组返回指针。用a, a + 5也可以，但长度写死容易出错。

对std::string排序字符：

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

void sortChars(std::string& s) {
std::sort(s.begin(), s.end());
}

std::string::iterator是随机访问迭代器，满足要求。按字节排序对 ASCII 没问题，对 UTF-8 中文则是按字节值排，不会得到拼音序，这一点要清楚。

关联容器（std::map、std::set）自身按比较器维持有序，不能对它们调用std::sort，也没有必要。std::unordered_map的元素类型是std::pair<const Key, T>，键是 const 的，不可赋值，无法排序；要排序只能把元素拷贝到std::vector再排。

常见坑点

1. 比较器写成<=❌[](int a, int b) { return a <= b; }—— 违反非自反性，是 UB。 ✅[](int a, int b) { return a < b; }。

2. 以为 sort 稳定❌ 先按姓名排序，再按分数排序，指望同分者保持姓名序。 ✅ 需要保持就用std::stable_sort，或把姓名作为第二关键字。

3. 对 list 调用 std::sort❌std::sort(lst.begin(), lst.end());—— 迭代器不是随机访问，编译失败。 ✅lst.sort();。

4. 比较器里修改元素❌[](Employee& a, Employee& b) { a.age += 1; return a.age < b.age; }—— 副作用导致行为未定义，参数也不该是非常量引用。 ✅ 比较器参数用const&，只读不写。

5. 浮点 NaN 参与比较❌ 直接对可能含 NaN 的std::vector<double>排序，比较器不构成严格弱序。 ✅ 先过滤或替换 NaN，或在比较器里显式规定 NaN 排在最后。

6. 对 unordered_map 直接排序❌std::sort(um.begin(), um.end());—— 元素键为 const，不可赋值，且迭代器不满足要求。 ✅ 把std::pair拷贝进std::vector，再按值排序。

7. 降序时混用<和>❌ 多关键字里一处写a.x > b.x，另一处写a.y >= b.y。 ✅ 每个关键字都只用严格比较，降序用>，升序用<。

8. 忘记<algorithm>❌ 只包含<vector>就调用std::sort，换一个标准库实现可能编译失败。 ✅ 显式包含<algorithm>，用到std::greater时再包含<functional>。

总结

std::sort的接口只有两个重载，难点几乎全在比较器上：只用严格小于、不修改元素、不引入 NaN 这类破坏严格弱序的值。选对算法同样重要——只需要前几名或中位数时，partial_sort与nth_element能省下大量不必要的工作，而需要稳定时应当明确改用stable_sort，不要指望sort碰巧保持次序。