C++STL函数和排序算法的快排以及归并排序详解

前言

排序是算法课的第一课，也是工程里最常见的操作。C++ 标准库提供了std::sort和std::stable_sort，日常代码直接调用即可；但面试和算法练习常要求手写快速排序与归并排序，理解它们的分治结构、复杂度来源和稳定性差异，仍然是必要的基本功。

一个高频误解是「std::sort就是快速排序」。标准只规定复杂度上界，不规定具体算法；主流实现使用内省排序（introsort），即快排、堆排、插入排序的混合：递归过深时切换到堆排，保证最坏 O(N log N)，小区间用插入排序减少开销。另一个误解是「比较函数写<=也能用」——比较器必须满足严格弱序（strict weak ordering），写<=是未定义行为。

本文先讲标准库排序函数的契约，再给出快速排序与归并排序的完整实现，最后对比三者的复杂度、稳定性与适用场景。示例以 C++17 为基准，所有代码按标准语义推演，具体运行时间依赖实现与数据，本文不给未测量的数字。

一、标准库的排序接口

std::sort声明在<algorithm>：

// 适用于 C++17（示意签名）
template<class RandomIt>
void sort(RandomIt first, RandomIt last);

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

template<class RandomIt>
void stable_sort(RandomIt first, RandomIt last);

template<class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);

要点：

• 
  
• 要求随机访问迭代器，所以std::vector、std::deque、std::array、原生数组可以，std::list不行（它有自己的成员sort）；
• 
  
• std::sort不保证稳定，相等元素的相对顺序可能改变；
• 
  
• std::stable_sort保证稳定，代价是需要额外内存；拿不到额外内存时复杂度可能退化到 O(N log² N)；
• 
  
• 两者都是 O(N log N) 次比较（std::sort自 C++11 起要求最坏 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 前面」。这个关系必须满足严格弱序：

1. 
   
2. 非自反：comp(x, x)为假；
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. 
   

用<=或>=作为比较器会违反非自反性，std::sort在遇到大量相等元素时可能越界访问，属于未定义行为（undefined behavior, UB）。正确写法是严格小于：

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

struct Person {
std::string name;
int age = 0;
};

void sort_people(std::vector<Person>& 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)。

下面的实现选取区间中点作为基准，用两个指针从两端向中间扫描并交换：

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

template <class T>
void quick_sort(std::vector<T>& 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)，且天然稳定——只要合并时「右边元素严格小于左边元素才取右边」，相等元素就会保持原有先后。

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

template <class T>
void merge_sort_impl(std::vector<T>& a, std::vector<T>& 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_cast<std::ptrdiff_t>(lo);
std::copy_n(buffer.begin() + offset, static_cast<std::ptrdiff_t>(hi - lo),
a.begin() + offset);
}

template <class T>
void merge_sort(std::vector<T>& a) {
std::vector<T> 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::sort；需要稳定用std::stable_sort；数据在链表上且不想搬移元素，用std::list::sort；数据大到内存放不下，考虑外部归并。手写快排和归并主要用于理解原理或特殊约束下的定制。

常见坑点

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

✅ 必须满足严格弱序；相等时返回false，用<。

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

✅std::sort不保证稳定；需要稳定时用std::stable_sort。

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

✅std::sort要求随机访问迭代器；链表用成员函数sort()。

1. 
   
2. ❌ 快排分区后不移动指针，遇到重复元素死循环。
3. 
   

✅ 交换后++i、--j，确保区间每轮收缩。

1. 
   
2. ❌ 快排内层扫描不检查边界，基准为极值时越界。
3. 
   

✅ 加i <= hi、j >= lo；或用三路划分与内省策略。

1. 
   
2. ❌ 归并时用a[j] <= a[i]判断取右边。
3. 
   

✅ 相等时先取左边，才是稳定排序；严格小于才取右边。

1. 
   
2. ❌ 手写归并每层递归都新建临时数组。
3. 
   

✅ 预分配一块与输入等长的 buffer，递归中复用。

1. 
   
2. ❌ 用std::sort排std::vector<bool>后对其元素取地址。
3. 
   

✅vector<bool>是特化代理引用，不提供真实元素地址；需要地址时换vector<char>或deque<bool>。

总结

排序算法的选择本质是三个约束的权衡：时间上界、额外空间、稳定性。标准库已经把通用场景覆盖得很好，手写实现的价值在于理解分治与合并的边界条件——尤其是「指针怎么走、区间怎么收」这两件事，几乎所有快排 bug 都出在这里。