什么是C++排序算法？

在C++中，“排序算法”通常指两大类：标准库（STL）中封装好的现成排序函数，以及开发者为了特定场景手写的排序逻辑。但在绝大多数工程语境下，它特指<algorithm>头文件里提供的泛型排序函数模板。

你可以把 C++ 排序算法理解为一套性能优异、高度泛化、开箱即用的排序“武器库”

1. 主力工具：std::sort（最强王者）

这是最常用的排序函数。底层实现是内省排序（Introsort）——它结合了快速排序（分区）、堆排序（防止最坏情况退化为 O(n²)）和插入排序（处理小规模数据）的优点。时间复杂度稳定在O(n log n)，且极致优化，日常开发无脑用它即可。

#include <algorithm> #include <vector> std::vector<int> v = {4, 2, 5, 1, 3}; std::sort(v.begin(), v.end()); // 默认升序：1,2,3,4,5

2. 特殊场景的“兄弟姐妹”

C++ 针对不同需求提供了精准的函数，选对才能事半功倍：

• std::stable_sort（稳定排序）：如果两个元素相等，它能保证排序后它们的相对顺序不变（std::sort不保证稳定）。底层基于归并排序，时间复杂度 O(n log n)，但内存开销稍大。

• std::partial_sort（部分排序）：你只关心前 N 个最小（或最大）的元素。例如“找出成绩前三名”，它只需 O(n log N) 的时间，比全排快得多。

• std::nth_element（求第K大）：它不完整排序，只把第 K 个位置的元素放到正确位置，左边全比它小，右边全比它大。复杂度O(n)，是快速“找中位数”或“分割数据”的利器。

3. 高度的灵活性与自定义

所有排序算法都支持传入自定义比较函数（Lambda、函数指针或仿函数），让你随心所欲地定义“小于”的规则：

// 按字符串长度降序排序 std::sort(v.begin(), v.end(), [](const std::string& a, const std::string& b) { return a.length() > b.length(); });

4. 适用范围极广（泛型）

它是模板函数，不局限于数组或特定容器。只要传入选代器（Iterator），它能排vector、deque、原始数组，甚至自定义链表的部分区间。

⚠️ 避坑指南（针对新手）

• 关联容器无需排序：std::set和std::map本身就有序，不能（也无需）对其使用std::sort。

• 链表用专属算法：std::list的迭代器不是随机访问迭代器，无法用std::sort，必须使用其成员函数list::sort()。

• 性能陷阱：std::sort要求随机访问迭代器，且比较操作必须满足“严格弱序”（即如果a<b为假且b<a为假，则视为等价）。

如果你是想面试手撕，那么快排、归并、堆排才是考察重点；但如果是工程开发，请坚决相信std::sort的标准库实现——它比绝大多数工程师手写的代码都要快且稳。

资源推荐

《C++八股文》2026版

贪心算法