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. 对任意 a,comp(a, a)为false(非自反);

  2. 若comp(a, b)为真,则comp(b, a)为假(非对称);

  3. 若comp(a, b)且comp(b, c),则comp(a, c)(传递);

  4. 不可比较的元素之间满足传递性(等价关系传递)。


写成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::sort替代方案



std::vector可以无

std::array可以无

普通数组可以(指针作迭代器)无

std::deque可以无

std::list不可以(非随机访问)成员sort()

std::forward_list不可以成员sort()

std::map/std::set不需要插入时自动有序



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


常见坑点



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


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



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


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



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


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



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


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



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


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



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


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



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


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



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


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


总结




用法写法说明



升序std::sort(v.begin(), v.end())默认operator<

降序std::sort(v.begin(), v.end(), std::greater<>{})需要<functional>

自定义std::sort(begin, end, comp)comp必须严格弱序

稳定std::stable_sort(...)保留相等元素相对顺序

前 K 个std::partial_sort(first, middle, last)只保证前段有序

第 K 小std::nth_element(...)平均线性

链表lst.sort()成员函数,稳定



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




相关新闻

Java Web网上作业批改系统(Servlet+JSP+MySQL)

Java Web网上作业批改系统(Servlet+JSP+MySQL)

简介&#xff1a;这是一套基于Java Web技术栈开发的网上作业批改系统完整源码&#xff0c;面向高校计算机专业课程设计、毕业设计及Java初学者实践项目。系统采用B/S架构&#xff0c;后端以JavaServlet实现业务逻辑&#xff0c;前端使用JSPCSSJavaScript构建交互界面&#xff0…

2026/11/16 19:51:26 阅读更多 →
插件化知识工作流:从收藏到行动的一体化实践

插件化知识工作流:从收藏到行动的一体化实践

知识工作者最头疼的从来不是“找不到工具”&#xff0c;而是工具太多、信息太碎、流程断档。你收藏了一堆好文章&#xff0c;最后只是在收藏夹里吃灰&#xff1b;你记了一堆笔记&#xff0c;回顾时发现根本想不起来当时为什么存。我自己折腾了很久之后&#xff0c;得出一个结论…

2026/11/16 14:36:27 阅读更多 →
AI辅助学术专著:分离研究层与表达层的高效写作方法

AI辅助学术专著:分离研究层与表达层的高效写作方法

前阵子我带着某高校的一个科研团队完成了《某领域智能评估方法与应用》这本约15万字的学术专著。整本书从定框架到交付排版稿&#xff0c;用了不到两个月。很多人听到这个周期&#xff0c;第一反应是“是不是用了AI代写&#xff1f;”我的回答很直接&#xff1a;AI确实深度参与…

2026/11/15 18:32:23 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻