七种比较类排序算法：步骤、实现与复杂度
排序算法是算法学习的第一课，也是面试的高频考点。本文整理七种比较类排序算法：冒泡、选择、插入、希尔、归并、快速、堆，每种给出思路、步骤、C++ 实现和复杂度分析，最后给一张总览表与选型建议。计数、基数、桶等非比较类排序不在本文范围内。
参考资料：菜鸟教程：十大经典排序算法
分类维度
排序算法主要按稳定性、就地性、自适应性三个维度分类。理想的排序算法具有以下特性：
- 具有稳定性，即相等元素的相对位置不变化；
- 具有就地性，即不使用额外的辅助空间；
- 具有自适应性，即时间复杂度受元素分布影响。
冒泡排序
算法步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
基础实现：
cpp
template <typename T>
void bubbleSort1(vector<T>& arr) {
for (int i = 0; i < arr.size(); ++i) {
for (int j = 0; j < arr.size() - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}经过优化的写法：用一个变量记录当前轮次是否发生过交换，没有发生交换说明已经有序，提前结束：
cpp
template <typename T>
void bubbleSort2(vector<T>& arr) {
bool swapped = true;
for (int i = 0; i < arr.size(); ++i) {
if (!swapped) break; // 上一轮没有发生交换，说明已经有序
swapped = false;
for (int j = 0; j < arr.size() - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
}
}优化版的最好情况（已有序）是 O(n)。冒泡排序稳定，但交换次数多，实践价值主要在教学。
选择排序
算法步骤：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
cpp
template <typename T>
void selectionSort(vector<T>& arr) {
for (int i = 0; i < arr.size(); ++i) {
int minIdx = i;
for (int j = i + 1; j < arr.size(); ++j) {
if (arr[minIdx] > arr[j]) {
minIdx = j;
}
}
swap(arr[i], arr[minIdx]);
}
}比较次数固定为 O(n²)，交换最多 n-1 次，交换次数少是它相对冒泡的唯一优势。注意它不稳定：跨越式的 swap 可能改变相等元素的相对位置（例如序列 5 8 5 2 9，第一轮 2 与第一个 5 交换后，两个 5 的相对顺序颠倒了）。
插入排序
算法步骤：
- 将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（与相等元素相等时，插到相等元素的后面，以此保证稳定）。
cpp
template<typename T>
void insertionSort(vector<T>& arr) {
for (int i = 1; i < arr.size(); ++i) {
int j = i - 1;
T key = arr[i];
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j--];
}
arr[j + 1] = key;
}
}小规模数据（几十到几百个元素）的实际表现通常好于快排、归并，因为常数小、且对基本有序的序列接近 O(n)。标准库的 introsort 在递归到小区间时改用插入排序，正是利用了这一点。
希尔排序
希尔排序（递减增量排序）是插入排序的改进版，基于插入排序的两点性质：
- 插入排序对几乎已经排好序的数据效率高，可以达到线性排序的效率；
- 但插入排序每次只能将数据移动一位，平均情况下的移动次数多。
基本思想：先按较大增量把序列分割成若干子序列分别做直接插入排序，待整个序列「基本有序」时，再对全体记录做一次直接插入排序。
算法步骤：
- 选择一个增量序列
t1, t2, ..., tk，其中ti > tj, tk = 1； - 按增量序列个数
k，对序列进行k趟排序； - 每趟排序，根据对应的增量
ti，将待排序列分割成若干子序列，分别对各子序列进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理。
cpp
// 增量序列 1, 4, 13, 40, ...（Knuth 序列）
template<typename T>
void shellSort(vector<T>& array) {
int gap = 1;
int n = array.size();
while (gap < n / 3) // 确定分组间隔
{
gap = gap * 3 + 1;
}
while (gap >= 1)
{
for (int i = gap; i < n; ++i) {
T key = array[i];
int j = i - gap;
while (j >= 0 && key < array[j])
{
array[j + gap] = array[j];
j -= gap;
}
array[j + gap] = key;
}
gap = gap / 3;
}
}复杂度取决于增量序列，Knuth 序列下平均约 O(n^1.3)。希尔排序不稳定：相同元素可能在不同的子序列中被分开排序。
归并排序
分治思路：递归划分区间，各自有序后合并。合并时左半元素与右半相等时优先取左半（代码中的 <=），保证稳定性。
cpp
template<typename T>
void mergeSort(vector<T> &vec, int left ,int right) {
if(left >= right)
return;
// 划分
int mid = (left + right) / 2;
mergeSort(vec, left, mid); // [l,mid] 有序
mergeSort(vec, mid + 1, right); // [mid+1,r] 有序
// 合并
vector<T> tmp(vec.begin()+left, vec.begin()+right + 1);
int i = 0;
int j = mid - left + 1;
for (int k = left; k <= right; ++k){
if(left + i > mid) {
vec[k] = tmp[j++];
} else if (left + j > right || tmp[i] <= tmp[j]) // <= 稳定
{
vec[k] = tmp[i++];
} else {
vec[k] = tmp[j++];
}
}
}时间复杂度稳定在 O(n log n)，最好最坏都一样；代价是 O(n) 的辅助数组。它是七种算法中唯一又快又稳定的，要求稳定排序时是首选。
快速排序
算法步骤：
- 从数列中挑出一个元素，称为「基准」（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
cpp
template<typename T>
int partitionVec(vector<T> &vec, int l, int r) {
// 以 vec[l] 作为基准
int i = l;
int j = r;
while (i < j)
{
while (i < j && vec[j] >= vec[l])
--j;
while(i < j && vec[i] <= vec[l])
++i;
swap(vec[i], vec[j]);
}
swap(vec[l], vec[i]);
return i;
}
template <typename T>
void quickSort(vector<T> &vec, int l, int r) {
// 子数组的长度为 1 时终止递归
if(l >= r)
return;
// 哨兵划分
int pos = partitionVec(vec, l, r);
// 左右数组递归
quickSort(vec, l, pos - 1);
quickSort(vec, pos + 1, r);
}平均 O(n log n) 且常数小，实际通常是综合最快的通用排序；最坏 O(n²) 出现在基准总选到最值时（如已有序序列取首元素做基准），工程实现用随机取基准、三数取中或递归深度超限时转堆排序（introsort）来规避。空间 O(log n) 为递归栈。不稳定。
堆排序
堆排序利用堆这种数据结构排序。堆积是近似完全二叉树的结构，子节点的键值总是小于（或者大于）它的父节点。可以把堆排序理解为利用堆的概念来实现的选择排序：
- 大顶堆：每个节点的值都大于或等于其子节点的值，用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，用于降序排列。
堆排序的平均时间复杂度为 $O(n\text{log}n)$。
算法步骤：
- 创建一个堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互换；
- 把堆的尺寸缩小 1，并调用 shift_down(0)，把新的数组顶端数据调整到相应位置；
- 重复步骤 2，直到堆的尺寸为 1。
用数组存储堆结构：下标为 $i$ 的节点的父节点下标为 $(i-1)/2$，左子节点下标为 $i \times 2 + 1$，右子节点下标为 $i \times 2 + 2$。
cpp
template <typename T>
void max_heapify(vector<T> &vec, int start, int end) {
int parent = start;
int child = parent * 2 + 1; // 左子节点下标
while (child <= end)
{
if(child + 1 <= end && vec[child] < vec[child + 1])
++child;
if (vec[parent] > vec[child]) {
return;
} else {
swap(vec[parent], vec[child]);
parent = child;
child = parent * 2 + 1;
}
}
}
template <typename T>
void heap_sort(vector<T> &vec) {
int len = vec.size();
for (int i = len / 2 - 1; i >= 0; --i) {
max_heapify(vec, i, len - 1); // 初始化堆，从最后一个根结点开始调整
}
for (int i = len - 1; i > 0; --i) {
swap(vec[0], vec[i]); // 将根节点（最大元素）与最后一个元素交换
max_heapify(vec, 0, i - 1); // 将堆的尺寸缩小 1，再进行调整
}
}最坏情况也是 O(n log n)，没有快排的退化问题，且只需 O(1) 额外空间；但访问模式跳跃（父子上标距离远），缓存不友好，实测通常慢于快排。不稳定。
总览与选型
| 算法 | 平均时间 | 最坏时间 | 最好时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$（优化版） | $O(1)$ | 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |
| 希尔排序 | 依增量序列 | 依增量序列 | $O(n)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | 稳定 |
| 快速排序 | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(\log n)$ | 不稳定 |
| 堆排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | 不稳定 |
选型要点：
- 小规模或基本有序：插入排序，常数小、对有序输入自适应
- 通用场景：快速排序（实际工程里直接用
std::sort，其 introsort 实现在快排基础上规避了最坏情况，小区间转插入排序） - 要求稳定：归并排序（
std::stable_sort通常为归并实现） - 内存受限且要最坏保证：堆排序（
std::partial_sort/nth_element也基于堆） - 希尔排序适合嵌入式等不便递归的场景，代码量小、无额外内存
面试常考的延伸问题：为什么 std::sort 用 introsort 而不是纯快排（最坏保证）、快排基准选取策略、归并的稳定合并条件（<=）、堆的下标计算。