前言排序是算法课的第一课也是工程里最常见的操作。C 标准库提供了std::sort和std::stable_sort日常代码直接调用即可但面试和算法练习常要求手写快速排序与归并排序理解它们的分治结构、复杂度来源和稳定性差异仍然是必要的基本功。一个高频误解是「std::sort就是快速排序」。标准只规定复杂度上界不规定具体算法主流实现使用内省排序introsort即快排、堆排、插入排序的混合递归过深时切换到堆排保证最坏 O(N log N)小区间用插入排序减少开销。另一个误解是「比较函数写也能用」——比较器必须满足严格弱序strict weak ordering写是未定义行为。本文先讲标准库排序函数的契约再给出快速排序与归并排序的完整实现最后对比三者的复杂度、稳定性与适用场景。示例以 C17 为基准所有代码按标准语义推演具体运行时间依赖实现与数据本文不给未测量的数字。一、标准库的排序接口std::sort声明在algorithm// 适用于 C17示意签名templateclass RandomItvoid sort(RandomIt first, RandomIt last);templateclass RandomIt, class Comparevoid sort(RandomIt first, RandomIt last, Compare comp);templateclass RandomItvoid stable_sort(RandomIt first, RandomIt last);templateclass RandomIt, class Comparevoid stable_sort(RandomIt first, RandomIt last, Compare comp);要点要求随机访问迭代器所以std::vector、std::deque、std::array、原生数组可以std::list不行它有自己的成员sortstd::sort不保证稳定相等元素的相对顺序可能改变std::stable_sort保证稳定代价是需要额外内存拿不到额外内存时复杂度可能退化到 O(N log² N)两者都是 O(N log N) 次比较std::sort自 C11 起要求最坏 O(N log N)。C 语言遗留的std::qsort在cstdlib签名为void qsort(void* base, std::size_t count, std::size_t size, int (*comp)(const void*, const void*))。它通过void*擦除类型比较函数还要把指针转回具体类型既容易写错也通常比模板版本难优化。C 代码应优先用std::sort。二、比较器与严格弱序排序算法只依赖一个关系comp(a, b)表示「a 应当排在 b 前面」。这个关系必须满足严格弱序非自反comp(x, x)为假非对称若comp(a, b)为真则comp(b, a)为假传递若comp(a, b)且comp(b, c)则comp(a, c)等价传递若 a 与 b 不可比、b 与 c 不可比则 a 与 c 也不可比。用或作为比较器会违反非自反性std::sort在遇到大量相等元素时可能越界访问属于未定义行为undefined behavior, UB。正确写法是严格小于// 适用于 C17#include algorithm#include string#include vectorstruct Person {std::string name;int age 0;};void sort_people(std::vectorPerson people) {std::sort(people.begin(), people.end(),[](const Person a, const Person b) {return a.age b.age; // 不要写 });}如果业务要求「年龄相同则保持原顺序」应使用std::stable_sort而不是在比较器里加入与输入顺序相关的判断。三、手写快速排序与归并排序快速排序的思路是选一个基准值pivot把区间分成「小于基准」和「不小于基准」两部分再对两部分递归。平均复杂度 O(N log N)最坏 O(N²)例如每次选到最大或最小值作为基准额外空间来自递归栈平均 O(log N)最坏 O(N)。下面的实现选取区间中点作为基准用两个指针从两端向中间扫描并交换// 适用于 C17#include utility#include vectortemplate class Tvoid quick_sort(std::vectorT a, int lo, int hi) {if (lo hi) {return;}int i lo;int j hi;const T pivot a[lo (hi - lo) / 2];while (i j) {while (i hi a[i] pivot) {i;}while (j lo pivot a[j]) {--j;}if (i j) {std::swap(a[i], a[j]);i;--j;}}quick_sort(a, lo, j);quick_sort(a, i, hi);}几个细节决定了它是否正确两个内层循环都带i hi/j lo的边界检查防止基准值恰好是极值时越界交换后i、--j保证区间收缩否则遇到相等元素会死循环递归调用的是[lo, j]和[i, hi]当j lo或i hi时由开头的lo hi兜住。这个版本对含大量重复元素的数组仍然可能退化所有元素相等时每轮只把区间缩小常数个位置。工程实现通常用三路划分小于、等于、大于处理重复值。另一个改进是「小区间用插入排序」减少递归调用开销。基准选择直接影响最坏情况。选首元素时已排序数组会退化成 O(N²)选中点能缓解常见的顺序输入但仍存在构造出的最坏输入。std::sort用内省排序解决这个问题记录递归深度超过阈值就改用堆排序把最坏复杂度压回 O(N log N)。归并排序把区间对半切开分别排序后再合并。合并需要一块与区间等长的辅助空间时间复杂度稳定在 O(N log N)且天然稳定——只要合并时「右边元素严格小于左边元素才取右边」相等元素就会保持原有先后。// 适用于 C17#include algorithm#include cstddef#include vectortemplate class Tvoid merge_sort_impl(std::vectorT a, std::vectorT buffer,std::size_t lo, std::size_t hi) {if (hi - lo 2) {return;}const std::size_t mid lo (hi - lo) / 2;merge_sort_impl(a, buffer, lo, mid);merge_sort_impl(a, buffer, mid, hi);std::size_t i lo;std::size_t j mid;std::size_t k lo;while (i mid j hi) {if (a[j] a[i]) {buffer[k] a[j]; // 严格小于才取右边保证稳定} else {buffer[k] a[i];}}while (i mid) {buffer[k] a[i];}while (j hi) {buffer[k] a[j];}const auto offset static_caststd::ptrdiff_t(lo);std::copy_n(buffer.begin() offset, static_caststd::ptrdiff_t(hi - lo),a.begin() offset);}template class Tvoid merge_sort(std::vectorT a) {std::vectorT buffer(a.size());merge_sort_impl(a, buffer, 0, a.size());}注意merge_sort_impl的区间是左闭右开[lo, hi)所以hi可以等于a.size()不会越界。buffer在整个递归过程中复用避免每层都分配新数组。归并排序的代价是 O(N) 额外空间。对std::vector这种连续存储额外空间通常可以接受对链表归并反而是优势——std::list::sort就是基于归并的成员函数不需要随机访问。四、三者对比与选择算法平均时间最坏时间额外空间稳定性适用场景std::sortO(N log N)O(N log N)O(log N) 栈否通用默认首选std::stable_sortO(N log N)O(N log² N) 无额外内存时O(N)是需要保持相等元素顺序手写快排O(N log N)O(N²)O(log N) 栈否教学、算法练习手写归并O(N log N)O(N log N)O(N)是链表、外部排序、要求稳定std::qsort取决于实现取决于实现取决于实现否维护 C 接口时选择顺序可以简化为默认std::sort需要稳定用std::stable_sort数据在链表上且不想搬移元素用std::list::sort数据大到内存放不下考虑外部归并。手写快排和归并主要用于理解原理或特殊约束下的定制。常见坑点❌ 比较器写成return a.x b.x;。✅ 必须满足严格弱序相等时返回false用。❌ 认为std::sort稳定依赖相等元素的原有顺序。✅std::sort不保证稳定需要稳定时用std::stable_sort。❌ 对std::list调用std::sort。✅std::sort要求随机访问迭代器链表用成员函数sort()。❌ 快排分区后不移动指针遇到重复元素死循环。✅ 交换后i、--j确保区间每轮收缩。❌ 快排内层扫描不检查边界基准为极值时越界。✅ 加i hi、j lo或用三路划分与内省策略。❌ 归并时用a[j] a[i]判断取右边。✅ 相等时先取左边才是稳定排序严格小于才取右边。❌ 手写归并每层递归都新建临时数组。✅ 预分配一块与输入等长的 buffer递归中复用。❌ 用std::sort排std::vectorbool后对其元素取地址。✅vectorbool是特化代理引用不提供真实元素地址需要地址时换vectorchar或dequebool。总结概念要点std::sort内省排序最坏 O(N log N)不稳定std::stable_sort稳定通常需要 O(N) 辅助空间严格弱序比较器必须非自反、非对称、可传递快排平均 O(N log N)最坏 O(N²)原地但不稳定归并稳定 O(N log N)需要 O(N) 辅助空间稳定性相等元素相对顺序是否保持排序算法的选择本质是三个约束的权衡时间上界、额外空间、稳定性。标准库已经把通用场景覆盖得很好手写实现的价值在于理解分治与合并的边界条件——尤其是「指针怎么走、区间怎么收」这两件事几乎所有快排 bug 都出在这里。
前言排序是算法课的第一课也是工程里最常见的操作。C 标准库提供了std::sort和std::stable_sort日常代码直接调用即可但面试和算法练习常要求手写快速排序与归并排序理解它们的分治结构、复杂度来源和稳定性差异仍然是必要的基本功。一个高频误解是「std::sort就是快速排序」。标准只规定复杂度上界不规定具体算法主流实现使用内省排序introsort即快排、堆排、插入排序的混合递归过深时切换到堆排保证最坏 O(N log N)小区间用插入排序减少开销。另一个误解是「比较函数写也能用」——比较器必须满足严格弱序strict weak ordering写是未定义行为。本文先讲标准库排序函数的契约再给出快速排序与归并排序的完整实现最后对比三者的复杂度、稳定性与适用场景。示例以 C17 为基准所有代码按标准语义推演具体运行时间依赖实现与数据本文不给未测量的数字。一、标准库的排序接口std::sort声明在algorithm// 适用于 C17示意签名templateclass RandomItvoid sort(RandomIt first, RandomIt last);templateclass RandomIt, class Comparevoid sort(RandomIt first, RandomIt last, Compare comp);templateclass RandomItvoid stable_sort(RandomIt first, RandomIt last);templateclass RandomIt, class Comparevoid stable_sort(RandomIt first, RandomIt last, Compare comp);要点要求随机访问迭代器所以std::vector、std::deque、std::array、原生数组可以std::list不行它有自己的成员sortstd::sort不保证稳定相等元素的相对顺序可能改变std::stable_sort保证稳定代价是需要额外内存拿不到额外内存时复杂度可能退化到 O(N log² N)两者都是 O(N log N) 次比较std::sort自 C11 起要求最坏 O(N log N)。C 语言遗留的std::qsort在cstdlib签名为void qsort(void* base, std::size_t count, std::size_t size, int (*comp)(const void*, const void*))。它通过void*擦除类型比较函数还要把指针转回具体类型既容易写错也通常比模板版本难优化。C 代码应优先用std::sort。二、比较器与严格弱序排序算法只依赖一个关系comp(a, b)表示「a 应当排在 b 前面」。这个关系必须满足严格弱序非自反comp(x, x)为假非对称若comp(a, b)为真则comp(b, a)为假传递若comp(a, b)且comp(b, c)则comp(a, c)等价传递若 a 与 b 不可比、b 与 c 不可比则 a 与 c 也不可比。用或作为比较器会违反非自反性std::sort在遇到大量相等元素时可能越界访问属于未定义行为undefined behavior, UB。正确写法是严格小于// 适用于 C17#include algorithm#include string#include vectorstruct Person {std::string name;int age 0;};void sort_people(std::vectorPerson people) {std::sort(people.begin(), people.end(),[](const Person a, const Person b) {return a.age b.age; // 不要写 });}如果业务要求「年龄相同则保持原顺序」应使用std::stable_sort而不是在比较器里加入与输入顺序相关的判断。三、手写快速排序与归并排序快速排序的思路是选一个基准值pivot把区间分成「小于基准」和「不小于基准」两部分再对两部分递归。平均复杂度 O(N log N)最坏 O(N²)例如每次选到最大或最小值作为基准额外空间来自递归栈平均 O(log N)最坏 O(N)。下面的实现选取区间中点作为基准用两个指针从两端向中间扫描并交换// 适用于 C17#include utility#include vectortemplate class Tvoid quick_sort(std::vectorT a, int lo, int hi) {if (lo hi) {return;}int i lo;int j hi;const T pivot a[lo (hi - lo) / 2];while (i j) {while (i hi a[i] pivot) {i;}while (j lo pivot a[j]) {--j;}if (i j) {std::swap(a[i], a[j]);i;--j;}}quick_sort(a, lo, j);quick_sort(a, i, hi);}几个细节决定了它是否正确两个内层循环都带i hi/j lo的边界检查防止基准值恰好是极值时越界交换后i、--j保证区间收缩否则遇到相等元素会死循环递归调用的是[lo, j]和[i, hi]当j lo或i hi时由开头的lo hi兜住。这个版本对含大量重复元素的数组仍然可能退化所有元素相等时每轮只把区间缩小常数个位置。工程实现通常用三路划分小于、等于、大于处理重复值。另一个改进是「小区间用插入排序」减少递归调用开销。基准选择直接影响最坏情况。选首元素时已排序数组会退化成 O(N²)选中点能缓解常见的顺序输入但仍存在构造出的最坏输入。std::sort用内省排序解决这个问题记录递归深度超过阈值就改用堆排序把最坏复杂度压回 O(N log N)。归并排序把区间对半切开分别排序后再合并。合并需要一块与区间等长的辅助空间时间复杂度稳定在 O(N log N)且天然稳定——只要合并时「右边元素严格小于左边元素才取右边」相等元素就会保持原有先后。// 适用于 C17#include algorithm#include cstddef#include vectortemplate class Tvoid merge_sort_impl(std::vectorT a, std::vectorT buffer,std::size_t lo, std::size_t hi) {if (hi - lo 2) {return;}const std::size_t mid lo (hi - lo) / 2;merge_sort_impl(a, buffer, lo, mid);merge_sort_impl(a, buffer, mid, hi);std::size_t i lo;std::size_t j mid;std::size_t k lo;while (i mid j hi) {if (a[j] a[i]) {buffer[k] a[j]; // 严格小于才取右边保证稳定} else {buffer[k] a[i];}}while (i mid) {buffer[k] a[i];}while (j hi) {buffer[k] a[j];}const auto offset static_caststd::ptrdiff_t(lo);std::copy_n(buffer.begin() offset, static_caststd::ptrdiff_t(hi - lo),a.begin() offset);}template class Tvoid merge_sort(std::vectorT a) {std::vectorT buffer(a.size());merge_sort_impl(a, buffer, 0, a.size());}注意merge_sort_impl的区间是左闭右开[lo, hi)所以hi可以等于a.size()不会越界。buffer在整个递归过程中复用避免每层都分配新数组。归并排序的代价是 O(N) 额外空间。对std::vector这种连续存储额外空间通常可以接受对链表归并反而是优势——std::list::sort就是基于归并的成员函数不需要随机访问。四、三者对比与选择算法平均时间最坏时间额外空间稳定性适用场景std::sortO(N log N)O(N log N)O(log N) 栈否通用默认首选std::stable_sortO(N log N)O(N log² N) 无额外内存时O(N)是需要保持相等元素顺序手写快排O(N log N)O(N²)O(log N) 栈否教学、算法练习手写归并O(N log N)O(N log N)O(N)是链表、外部排序、要求稳定std::qsort取决于实现取决于实现取决于实现否维护 C 接口时选择顺序可以简化为默认std::sort需要稳定用std::stable_sort数据在链表上且不想搬移元素用std::list::sort数据大到内存放不下考虑外部归并。手写快排和归并主要用于理解原理或特殊约束下的定制。常见坑点❌ 比较器写成return a.x b.x;。✅ 必须满足严格弱序相等时返回false用。❌ 认为std::sort稳定依赖相等元素的原有顺序。✅std::sort不保证稳定需要稳定时用std::stable_sort。❌ 对std::list调用std::sort。✅std::sort要求随机访问迭代器链表用成员函数sort()。❌ 快排分区后不移动指针遇到重复元素死循环。✅ 交换后i、--j确保区间每轮收缩。❌ 快排内层扫描不检查边界基准为极值时越界。✅ 加i hi、j lo或用三路划分与内省策略。❌ 归并时用a[j] a[i]判断取右边。✅ 相等时先取左边才是稳定排序严格小于才取右边。❌ 手写归并每层递归都新建临时数组。✅ 预分配一块与输入等长的 buffer递归中复用。❌ 用std::sort排std::vectorbool后对其元素取地址。✅vectorbool是特化代理引用不提供真实元素地址需要地址时换vectorchar或dequebool。总结概念要点std::sort内省排序最坏 O(N log N)不稳定std::stable_sort稳定通常需要 O(N) 辅助空间严格弱序比较器必须非自反、非对称、可传递快排平均 O(N log N)最坏 O(N²)原地但不稳定归并稳定 O(N log N)需要 O(N) 辅助空间稳定性相等元素相对顺序是否保持排序算法的选择本质是三个约束的权衡时间上界、额外空间、稳定性。标准库已经把通用场景覆盖得很好手写实现的价值在于理解分治与合并的边界条件——尤其是「指针怎么走、区间怎么收」这两件事几乎所有快排 bug 都出在这里。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
