排序简单整理
2026-08-19
排序的目标，是按照某个关键字把一组元素重新排列。算法题里经常只问“把整数从小到大排好”，但真正选择算法时，还要关心数据规模、是否接近有序、值域大小、能不能使用额外内存，以及相等元素的先后顺序能否改变。
这篇文章把常见排序方法放在一起整理。每种算法都先看一个小图，再看它的核心思路、复杂度和一份尽量短的 C++ 实现。
std::sort；学习手写排序的主要价值，是理解分治、堆、局部有序、计数和稳定性等思想，而不是在项目中重新造一个更快的 sort。
先认识四个评价指标
- 时间复杂度：数据量为
n时，大约需要多少次比较或移动。 - 空间复杂度：除原数组外，还需要多少额外空间。
- 稳定性：两个关键字相等的元素，排序后是否仍保持原来的先后顺序。
- 原地排序：是否只用常量级或很少的额外空间直接修改原数组。
稳定性在只有整数时不明显。假设学生记录按分数排序，小王(90) 原本在 小李(90) 前面；稳定排序会保留这个顺序。因此可以先按姓名排序，再稳定地按分数排序，得到“分数优先、同分时姓名有序”的结果。
| 算法 | 平均时间 | 最坏时间 | 额外空间 | 稳定 | 适合场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 是 | 教学、小规模且接近有序 |
| 选择排序 | O(n²) | O(n²) | O(1) | 否 | 写入代价高、数据很少 |
| 插入排序 | O(n²) | O(n²) | O(1) | 是 | 小数组、近乎有序 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 | 需要稳定、链表、外部排序 |
| 快速排序 | O(n log n) | O(n²) | 平均 O(log n) | 否 | 通用内存数组，缓存友好 |
| 希尔排序 | 取决于间隔 | 常见上界 O(n²) | O(1) | 否 | 中小规模、实现简单且不需额外空间 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | 要求最坏时间保证且空间严格 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 可稳定 | 整数值域 k 较小 |
| 桶排序 | 平均 O(n + k) | O(n²) | O(n + k) | 取决于桶内排序 | 分布较均匀 |
| 基数排序 | O(d(n + b)) | O(d(n + b)) | O(n + b) | 是 | 固定位数整数或字符串 |
其中 k 表示值域或桶数，d 表示处理的位数，b 表示每一位的进制。复杂度表只是第一层判断，常数、缓存访问和输入分布同样会影响实际速度。
基础比较排序
冒泡排序：较大的数逐轮浮到右边
从左向右比较相邻元素，如果左边更大就交换。完成一轮后，当前未排序部分的最大值一定到达最右端。若某一轮没有发生交换，说明数组已经有序，可以提前结束。
void bubbleSort(std::vector<int>& a) {
for (std::size_t end = a.size(); end > 1; --end) {
bool swapped = false;
for (std::size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
std::swap(a[i - 1], a[i]);
swapped = true;
}
}
if (!swapped) break;
}
}只有严格大于时才交换，相等元素不会越过彼此，所以冒泡排序是稳定的。带提前结束时，已经有序的输入只需 O(n)。
选择排序：每轮选出最小值
把数组分为左侧已排序区和右侧未排序区。每一轮从未排序区找出最小值，与未排序区第一个元素交换。
void selectionSort(std::vector<int>& a) {
for (std::size_t i = 0; i < a.size(); ++i) {
std::size_t minIndex = i;
for (std::size_t j = i + 1; j < a.size(); ++j) {
if (a[j] < a[minIndex]) minIndex = j;
}
if (minIndex != i) std::swap(a[i], a[minIndex]);
}
}选择排序无论输入是否有序，都要完成约 n²/2 次比较；但最多只交换 n - 1 次。一次远距离交换可能跨过相等元素，因此普通选择排序不稳定。
插入排序：把新牌插进有序手牌
假设左侧已经有序，取出右侧第一个元素作为 key，把比它大的元素依次右移，再把它放进空出的位置。它很像摸到一张新扑克牌后插入手牌。
void insertionSort(std::vector<int>& a) {
for (std::size_t i = 1; i < a.size(); ++i) {
int key = a[i];
std::size_t j = i;
while (j > 0 && a[j - 1] > key) {
a[j] = a[j - 1];
--j;
}
a[j] = key;
}
}数组越接近有序，需要移动的元素越少，最好时间为 O(n)。判断条件写成 a[j - 1] > key 而不是 >=，就不会越过相等元素，因此保持稳定。
分治排序
归并排序：先分开，再合并
归并排序把数组不断对半分，直到每段只剩一个元素。单个元素天然有序，再把相邻的两个有序段合并。合并时只比较两个段的队首，取较小者放入临时数组。
void mergeSortImpl(std::vector<int>& a, std::vector<int>& temp,
int left, int right) {
if (right - left <= 1) return;
const int mid = left + (right - left) / 2;
mergeSortImpl(a, temp, left, mid);
mergeSortImpl(a, temp, mid, right);
int i = left, j = mid, out = left;
while (i < mid && j < right) {
if (a[i] <= a[j]) temp[out++] = a[i++];
else temp[out++] = a[j++];
}
while (i < mid) temp[out++] = a[i++];
while (j < right) temp[out++] = a[j++];
for (int k = left; k < right; ++k) a[k] = temp[k];
}
void mergeSort(std::vector<int>& a) {
std::vector<int> temp(a.size());
mergeSortImpl(a, temp, 0, static_cast<int>(a.size()));
}每一层合并总共处理 n 个元素，一共有约 log n 层，所以时间始终是 O(n log n)。合并时相等就先取左段元素，才能保持稳定。代价是通常需要 O(n) 临时空间。
实战：LeetCode 148 排序链表
LeetCode 148. 排序链表要求把单链表按升序排列。链表最多有 5 × 10⁴ 个节点，进阶要求是 O(n log n) 时间与常数级额外空间。
这道题很适合归并排序。数组归并通常要创建临时数组，而链表可以直接修改 next 指针完成拆分和合并，不需要搬动节点。普通自顶向下归并虽然容易写，但递归调用栈需要 O(log n) 空间；若要满足进阶要求，应使用自底向上的迭代归并。
三个关键操作
- 计算长度：先遍历链表得到
n，方便控制合并轮数。 - 按长度断链：每轮把链表切成长度为
width的小段；最后一段不够长也没有关系。 - 合并并接回：稳定地合并相邻两段，并让
tail始终指向已排序部分的末尾。
class Solution {
// 从 head 开始保留 size 个节点并断链，返回下一段的头节点。
ListNode* split(ListNode* head, int size) {
while (--size > 0 && head != nullptr) {
head = head->next;
}
if (head == nullptr) return nullptr;
ListNode* nextPart = head->next;
head->next = nullptr;
return nextPart;
}
// 把两个有序链表接到 tail 后面，返回合并后的新尾节点。
ListNode* merge(ListNode* left, ListNode* right, ListNode* tail) {
ListNode* current = tail;
while (left != nullptr && right != nullptr) {
if (left->val <= right->val) {
current->next = left;
left = left->next;
} else {
current->next = right;
right = right->next;
}
current = current->next;
}
current->next = (left != nullptr) ? left : right;
while (current->next != nullptr) {
current = current->next;
}
return current;
}
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
int length = 0;
for (ListNode* node = head; node != nullptr; node = node->next) {
++length;
}
ListNode dummy(0, head);
for (int width = 1; width < length; width *= 2) {
ListNode* tail = &dummy;
ListNode* current = dummy.next;
while (current != nullptr) {
ListNode* left = current;
ListNode* right = split(left, width);
current = split(right, width);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
};步长依次为 1、2、4、8……，每一轮都会访问全部 n 个节点，共有 log n 轮，因此时间复杂度是 O(n log n)。算法只保存若干指针和计数器，额外空间是 O(1)。合并时相等就先连接左段节点，所以它也是稳定排序。
split 必须把前一段的尾节点指向 nullptr，否则两段仍然相连，合并时可能重复访问节点甚至形成环；每次合并后也必须更新 tail，下一组链表才能接到正确位置。
快速排序：让基准一次归位
选一个基准值 pivot，把小于等于它的元素放到左侧，更大的放到右侧；基准到达最终位置后，再递归处理两边。下面使用末尾元素作基准的 Lomuto 分区。
int partition(std::vector<int>& a, int left, int right) {
const int pivot = a[right];
int boundary = left;
for (int i = left; i < right; ++i) {
if (a[i] <= pivot) {
std::swap(a[i], a[boundary]);
++boundary;
}
}
std::swap(a[boundary], a[right]);
return boundary;
}
void quickSort(std::vector<int>& a, int left, int right) {
if (left >= right) return;
const int pivotIndex = partition(a, left, right);
quickSort(a, left, pivotIndex - 1);
quickSort(a, pivotIndex + 1, right);
}分区均衡时递归约 log n 层，总时间为 O(n log n)。若每次都选到最小或最大值，递归会退化成链，时间与栈深度分别变成 O(n²) 和 O(n)。随机选基准、三数取中和三路分区都能降低退化风险。分区中的跨越交换会改变相等元素的顺序，所以通常不稳定。
希尔排序与堆排序
希尔排序：先让元素大步接近目标位置
插入排序在近乎有序时很快，但一个小元素若在数组末尾，只能一步一步向前移动。希尔排序先选较大的间隔 gap，对相隔 gap 的元素做插入排序，再逐步缩小间隔，最后以 gap = 1 完成普通插入排序。
void shellSort(std::vector<int>& a) {
for (std::size_t gap = a.size() / 2; gap > 0; gap /= 2) {
for (std::size_t i = gap; i < a.size(); ++i) {
int value = a[i];
std::size_t j = i;
while (j >= gap && a[j - gap] > value) {
a[j] = a[j - gap];
j -= gap;
}
a[j] = value;
}
}
}希尔排序的复杂度高度依赖间隔序列，不能简单写成一个固定平均值。上面的折半间隔容易理解，但不一定最好。相等元素可能分到不同组并跨越移动，因此不稳定。
堆排序：反复取出最大值
大根堆是一棵完全二叉树，每个父节点都不小于子节点，因此根节点一定是最大值。数组可以直接表示堆：下标 i 的左右孩子是 2i + 1 和 2i + 2。
void siftDown(std::vector<int>& a, int root, int heapSize) {
while (true) {
int largest = root;
const int left = 2 * root + 1;
const int right = 2 * root + 2;
if (left < heapSize && a[left] > a[largest]) largest = left;
if (right < heapSize && a[right] > a[largest]) largest = right;
if (largest == root) return;
std::swap(a[root], a[largest]);
root = largest;
}
}
void heapSort(std::vector<int>& a) {
const int n = static_cast<int>(a.size());
for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, i, n);
for (int end = n - 1; end > 0; --end) {
std::swap(a[0], a[end]);
siftDown(a, 0, end);
}
}从最后一个非叶节点向前调整可以在线性时间建堆；随后取出 n 次堆顶，每次调整 O(log n)，总时间是 O(n log n)。它原地且最坏时间有保证，但访问位置跳跃，缓存局部性通常不如快速排序；交换堆顶也会破坏稳定性。
不基于比较的线性排序
只依靠“两个元素谁更小”的比较排序，在一般模型下最坏需要 Ω(n log n) 次比较。计数、桶和基数排序之所以有机会接近线性时间，是因为它们利用了整数值域、分布或数位结构等额外信息，并不是突破了比较排序的下界。
计数排序：统计每个值出现几次
如果数据都是整数且值域不大，可以创建计数数组。遍历输入统计频次，再按值从小到大把元素写回。处理负数时，用最小值作为偏移。
void countingSort(std::vector<int>& a) {
if (a.empty()) return;
const auto [minIt, maxIt] = std::minmax_element(a.begin(), a.end());
const int minValue = *minIt;
const int maxValue = *maxIt;
const std::int64_t range =
static_cast<std::int64_t>(maxValue) - minValue + 1;
std::vector<std::size_t> count(static_cast<std::size_t>(range));
for (int value : a) {
const auto offset = static_cast<std::int64_t>(value) - minValue;
++count[static_cast<std::size_t>(offset)];
}
std::size_t out = 0;
for (std::int64_t offset = 0; offset < range; ++offset) {
auto& frequency = count[static_cast<std::size_t>(offset)];
while (frequency > 0) {
a[out++] = static_cast<int>(offset + minValue);
--frequency;
}
}
}这份简化实现只排序整数值，没有保留附属记录，所以谈不上观察对象稳定性。若要稳定排序“带关键字的记录”，需把频次改为前缀和，并从输入末尾向前放入输出数组。还要先检查 max - min 是否合理：排序 5 个数却开几十亿个计数格显然得不偿失。
桶排序：先分区，再排桶内
桶排序把数值范围切成若干区间，每个元素先进入对应桶。桶内各自排序后，按桶的顺序拼接。若元素分布均匀，各桶都很小，总耗时可以接近线性。
void bucketSort(std::vector<int>& a, int bucketWidth) {
if (a.empty() || bucketWidth <= 0) return;
const auto [minIt, maxIt] = std::minmax_element(a.begin(), a.end());
const int minValue = *minIt;
const std::int64_t range =
static_cast<std::int64_t>(*maxIt) - minValue;
const std::size_t bucketCount =
static_cast<std::size_t>(range / bucketWidth + 1);
std::vector<std::vector<int>> buckets(bucketCount);
for (int value : a) {
const auto index = static_cast<std::size_t>(
(static_cast<std::int64_t>(value) - minValue) / bucketWidth);
buckets[index].push_back(value);
}
std::size_t out = 0;
for (auto& bucket : buckets) {
std::sort(bucket.begin(), bucket.end());
for (int value : bucket) a[out++] = value;
}
}桶宽过大时，大量元素挤进同一个桶，性能退化为桶内排序的复杂度；桶宽太小又会浪费大量空桶。桶排序的关键不是套公式，而是根据数据分布设计映射。稳定性取决于放桶、桶内排序和收集过程是否都保持顺序。
基数排序：按个位、十位、百位依次整理
最低位优先（LSD）基数排序先按个位稳定排序，再按十位稳定排序，直到最高位。后一次排序不能打乱前面数位已经形成的顺序，所以每一轮必须使用稳定排序，常见做法是稳定的计数排序。
void radixSortNonNegative(std::vector<int>& a) {
if (a.empty()) return;
const int maxValue = *std::max_element(a.begin(), a.end());
std::vector<int> output(a.size());
for (std::int64_t exp = 1; maxValue / exp > 0; exp *= 10) {
std::array<std::size_t, 10> count{};
for (int value : a) ++count[(value / exp) % 10];
for (std::size_t i = 1; i < count.size(); ++i) {
count[i] += count[i - 1];
}
for (std::size_t i = a.size(); i-- > 0; ) {
const int digit = static_cast<int>((a[i] / exp) % 10);
output[--count[digit]] = a[i];
}
a.swap(output);
}
}这份版本只接受非负整数，并用 64 位 exp 避免乘 10 时溢出。若要处理负数，可以分离负数与非负数后分别处理，也可以对无符号位模式设计统一的字节级基数排序，但不能直接把负数塞进上面的十进制桶下标。
这些算法之间有什么联系
- 冒泡、选择、插入都容易手写，但处理普通大数组通常是
O(n²)；其中插入排序最值得作为小区间优化。 - 归并和快速都使用分治。归并先递归再合并，稳定但需要缓冲区；快速排序先分区再递归，通常原地且缓存友好。
- 希尔排序是分组的插入排序，先消灭远距离逆序；堆排序借助堆反复选择最大值，可看作改进的选择排序。
- 计数、桶、基数都利用关键字结构。计数排序按完整值计数，桶排序按范围分组，基数排序按数位反复稳定分组。
实际应该怎么选
- 普通 C++ 数组：使用
std::sort，平均和最坏都能获得可靠的O(n log n)级别表现。 - 必须稳定：使用
std::stable_sort，或在适合的场景使用归并排序。 - 数据很小或近乎有序：插入排序简单而且常数小；成熟通用排序也常在小区间切换到类似策略。
- 最坏时间必须是 O(n log n)，额外空间又很紧：考虑堆排序。
- 整数值域远小于数据量：计数排序可能非常合适。
- 数据分布已知且均匀：可以设计桶排序；先确认极端分布下的退化行为。
- 大量固定位数整数或字符串：基数排序有机会超过比较排序，但要考虑内存、位数和实现复杂度。
标准库的最小用法
#include <algorithm>
#include <vector>
std::vector<int> values{5, 2, 4, 1};
std::sort(values.begin(), values.end()); // 升序
std::sort(values.begin(), values.end(), std::greater<>{}); // 降序
struct Student { std::string name; int score; };
std::vector<Student> students{/* ... */};
std::stable_sort(students.begin(), students.end(),
[](const Student& a, const Student& b) {
return a.score > b.score;
});a.score >= b.score。标准库比较器必须表达严格弱序；当两个元素相等时，comp(a, b) 和 comp(b, a) 都应为假。
最后的记忆线索
- 冒泡：交换相邻逆序对，最大值逐轮到右边。
- 选择：从未排序区选最小值，放到左边。
- 插入：左侧始终有序，把新元素插进去。
- 归并：拆成小段，两个有序段再合并。
- 快速：选基准做分区，让基准一次归位。
- 希尔：先大步分组插入，最后小步收尾。
- 堆：建大根堆，反复把最大值送到末尾。
- 计数：值不多，就数每个值出现几次。
- 桶：范围可分，就先分桶再排桶内。
- 基数：一位一位稳定排序，从低位推到高位。
真正掌握排序，不是背完十段模板，而是拿到数据后先问：我能利用哪些输入性质？是否要求稳定？空间是否受限？最坏情况能否接受？这些问题回答清楚，算法选择通常就不会太远。