冒泡排序是许多人学习C++时接触的第一个排序算法，它的原理直观、代码简短，非常适合用来理解排序的本质。但只掌握冒泡排序显然不够，面试和实际开发中经常要求对比多种排序算法的性能与适用场景。本文先详细讲解冒泡排序的标准写法和两种常见优化，再依次给出其余九大经典排序算法的完整C++实现代码，并分析它们的时间复杂度、空间复杂度和稳定性。
一、C++冒泡排序怎么写（含优化版本）
冒泡排序的基本思想是：从头到尾依次比较相邻的两个元素，如果前面的比后面的大就交换位置，这样一趟下来最大的元素就会“冒泡”到末尾。对n个元素执行n-1趟后，整个数组就有序了。
#include <iostream>
#include <vector>
using namespace std;
// 基础版冒泡排序
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) { // 一共进行 n-1 趟
for (int j = 0; j < n - 1 - i; j++) { // 每趟比较到未排序部分的末尾
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]); // 逆序则交换
}
}
}
}
int main() {
vector<int> arr = {5, 2, 9, 1, 7, 3};
bubbleSort(arr);
for (int x : arr) cout << x << " ";
return 0;
}</code>基础版有一个明显缺陷：即使数组在中途已经完全有序，外层循环依然会继续执行。经典面试考点就是如何优化这一点。做法是设置一个标志位，某一趟如果没有发生任何交换，说明数组已经有序，直接退出循环。
进一步的优化是“双向冒泡”，也叫鸡尾酒排序：每趟先从左往右把最大值冒到右边，再从右往左把最小值冒到左边，对于大部分元素已有序的数组效率更高。
// 优化版：提前退出 + 记录最后交换位置
void bubbleSortOpt(vector<int>& arr) {
int n = arr.size();
int lastSwap = n - 1;
while (lastSwap > 0) {
int boundary = lastSwap;
lastSwap = 0;
for (int j = 0; j < boundary; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
lastSwap = j; // 记录最后一次交换的位置
}
}
}
}冒泡排序的平均和最坏时间复杂度都是O(n²)，最好情况（已有序）优化后可达O(n)，空间复杂度O(1)，是稳定排序。数据量大时性能不佳，主要价值在于教学和理解排序思想。
二、简单排序家族：选择排序、插入排序、希尔排序
选择排序每一趟从未排序区间中选出最小元素，放到已排序区间的末尾。它的交换次数最少，最多只有n-1次交换，但不稳定，时间复杂度恒为O(n²)。
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx != i) swap(arr[i], arr[minIdx]);
}
}插入排序像整理扑克牌：把新元素插入到前面已排序的合适位置。它在数据基本有序或规模很小时表现极好，这也是STL中std::sort在小区间切换到插入排序的原因。平均O(n²)，最好O(n)，稳定。
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 后移腾位置
j--;
}
arr[j + 1] = key;
}
}希尔排序是插入排序的改进版，按增量将数组分组做插入排序，增量逐渐缩小到1。它的时间复杂度依赖于增量序列，约在O(n^1.3)到O(n²)之间，空间O(1)，不稳定。
void shellSort(vector<int>& arr) {
int n = arr.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
}三、高效比较排序：快速排序、归并排序、堆排序
快速排序是实践中最常用的排序之一。它选取一个基准值，将数组划分成小于和大于基准的两部分，再递归处理。平均时间复杂度O(n log n)，最坏退化为O(n²)，空间复杂度取决于递归深度，不稳定。
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 取最后一个元素为基准
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
swap(arr[++i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}归并排序采用分治思想，把数组不断二分直到单个元素，再两两合并有序子数组。它的时间复杂度稳定为O(n log n)，但需要O(n)的辅助空间，并且是稳定排序，适合链表排序和外部排序场景。
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> tmp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= right) tmp[k++] = arr[j++];
for (k = 0; k < (int)tmp.size(); k++) arr[left + k] = tmp[k];
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}堆排序先建立大顶堆，然后每次将堆顶元素与末尾交换并重新调整堆。时间复杂度稳定在O(n log n)，空间O(1)，不稳定，适合对空间要求苛刻的场景。
void heapify(vector<int>& arr, int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) // 建堆
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) { // 逐个取出堆顶
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}四、非比较排序：计数排序、桶排序、基数排序
这类算法不依赖元素间的比较，而是利用数值本身的性质，因此可以突破O(n log n)的下界，达到线性时间，但要求数据满足特定条件。
计数排序适合取值范围不大的整数。统计每个值出现的次数，再按顺序输出。时间复杂度O(n+k)，k为数据范围，稳定（下面采用前缀和的稳定写法）。
void countingSort(vector<int>& arr) {
if (arr.empty()) return;
int maxVal = *max_element(arr.begin(), arr.end());
vector<int> count(maxVal + 1, 0);
for (int x : arr) count[x]++;
for (int i = 1; i <= maxVal; i++) count[i] += count[i - 1]; // 前缀和
vector<int> output(arr.size());
for (int i = arr.size() - 1; i >= 0; i--) { // 逆序保证稳定
output[--count[arr[i]]] = arr[i];
}
arr = output;
}桶排序把数据分配到若干个桶里，每个桶内部单独排序后再拼接。桶的数量和映射函数直接影响性能，均匀分布时接近O(n)，最坏退化到O(n²)。它是对计数排序的推广，适合浮点数和均匀分布的数据。
void bucketSort(vector<float>& arr) {
int n = arr.size();
if (n == 0) return;
float maxVal = *max_element(arr.begin(), arr.end());
float minVal = *min_element(arr.begin(), arr.end());
int bucketCount = 10;
vector<vector<float>> buckets(bucketCount);
for (float x : arr) {
int idx = (int)((x - minVal) / (maxVal - minVal + 1e-9) * bucketCount);
buckets[idx].push_back(x);
}
for (auto& b : buckets) sort(b.begin(), b.end());
int k = 0;
for (auto& b : buckets)
for (float x : b) arr[k++] = x;
}基数排序按低位到高位依次做稳定排序（通常用计数排序），适合整数或定长字符串。d位数、基数r的情况下时间复杂度为O(d(n+r))，稳定，但要求数据能按位拆解。
void radixSort(vector<int>& arr) {
if (arr.empty()) return;
int maxVal = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
vector<int> output(arr.size());
vector<int> count(10, 0);
for (int x : arr) count[(x / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = arr.size() - 1; i >= 0; i--) {
int d = (arr[i] / exp) % 10;
output[--count[d]] = arr[i];
}
arr = output;
}
}五、十大排序算法对比与选择建议
下表汇总了十种算法的核心指标，方便快速查阅。
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
| 桶排序 | O(n) | O(n²) | O(n+k) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 |
实际编码中，如果不确定数据特点，直接使用标准库的std::sort即可，它内省排序的结合方案在各种场景下都有不错的表现。需要稳定排序时用std::stable_sort（基于归并）。手写算法更多出现在面试、竞赛和学习场景：小数据量或基本有序选插入排序，普通整型大范围数据选快速排序，内存紧张选堆排序，取值集中的整数选计数排序，浮点数均匀分布可尝试桶排序。
理解每一种排序的适用边界，比死记代码更重要。建议在掌握本文代码后，动手修改边界条件、观察不同数据分布下各算法的耗时差异，这样才能真正把排序算法内化成自己的能力。