1.冒泡排序(Bubble Sort)
思想
每轮从左到右扫描,相邻两个元素逆序就交换。一轮结束后,当前未排序部分的最大值必然被「冒」到最右端——像气泡上浮。
核心不变量:
第 k 轮结束后,最后 k 个元素已就位且有序。所以每轮的内层扫描范围可以缩短 1。
加一个提前退出优化:
某一轮如果一次交换都没发生,说明已有序,直接结束。
时间:
最好 O(n)(已有序 + 提前退出),平均/最坏 O(n²)
空间 :
O(1),稳定(相等元素只在严格大于时才交换,相对顺序不变)
代码
void bubbleSort(vector<int>& a) {
int n = a.size();
for (int end = n - 1; end > 0; --end) { // 每轮把最大值冒到 end
bool swapped = false;
for (int i = 0; i < end; ++i) {
if (a[i] > a[i + 1]) { // 严格大于 => 稳定
swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped) break; // 一轮无交换 => 已有序
}
}
2.快速排序(Quick Sort)
思想
1. 选一个基准值 pivot
2. 划分(partition):把数组重排成 [≤ pivot] [pivot] [≥ pivot]
3. 对左右两段递归重复
核心在划分,排序只是划分的副产品——pivot 每轮落到的位置就是它最终的位置,这个性质还衍生出快速选择算法(找第 k 大,平均 O(n))。
时间:
平均 O(n log n),最坏 O(n²)(每次划分都极端不均,如已排序数组总取首元素当 pivot)
空间:
递归栈平均 O(log n)
是否稳定:
不稳定,原地(不需要额外数组)
实践中是最快的通用排序:划分是顺序扫描、交换在数组内部进行,cache 局部性极好
代码(随机基准 + Hoare 划分 + 小区间插排优化)
#include <vector>
#include <utility>
// Lomuto 分区:以 a[hi] 为 pivot,返回 pivot 最终位置
int partition(std::vector<int>& a, int lo, int hi) {
int pivot = a[hi];
int i = lo; // i 指向"≤ pivot 区域"的下一个空位
for (int j = lo; j < hi; ++j) {
if (a[j] <= pivot) {
std::swap(a[i], a[j]);
++i;
}
}
std::swap(a[i], a[hi]); // pivot 放到正确位置
return i;
}
void quickSort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
void quickSort(std::vector<int>& a) {
if (!a.empty()) quickSort(a, 0, (int)a.size() - 1);
}
值得知道的点:
- 随机基准把最坏情况从「特定输入必触发」变成「概率上几乎不发生」,这是工程标配;再进一步是三数取中(取首中尾的中位数)
3.归并排序(Merge Sort)
思想
1. 把数组从中间分成两半,分别递归排好
2. 合并(merge):双指针比较两个有序段的头部,依次取较小者放入临时数组
核心在合并两个有序序列——这个操作本身还独立出现在合并两个有序链表、外部排序等场景。
时间:
任何输入都是 O(n log n),没有最坏退化
空间 :
O(n)(临时数组)
稳定:
(合并时左边元素优先于右边相等元素)
访存模式是顺序读写,对链表排序、外部排序天然友好
代码
void mergeSort(vector<int>& a, vector<int>& tmp, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(a, tmp, l, mid);
mergeSort(a, tmp, mid + 1, r);
if (a[mid] <= a[mid + 1]) return; // 已有序,跳过合并(重要优化)
// 合并 [l, mid] 和 [mid+1, r]
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++]; // <= 取左边 => 稳定
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
copy(tmp.begin() + l, tmp.begin() + r + 1, a.begin() + l);
}
void mergeSort(vector<int>& a) {
vector<int> tmp(a.size());
mergeSort(a, tmp, 0, (int)a.size() - 1);
}
4.完整测试 main
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> data = {9, 3, 7, 1, 8, 3, 5, 2, 6, 4};
auto a = data; bubbleSort(a);
auto b = data; quickSort(b);
auto c = data; mergeSort(c);
for (int x : a) cout << x << ' '; cout << "(bubble)\n";
for (int x : b) cout << x << ' '; cout << "(quick)\n";
for (int x : c) cout << x << ' '; cout << "(merge)\n";
}
稳定性指的是:值相等的元素,排序后是否保持它们原来的先后顺序。
5.外部排序
快速排序,归并排序均为数据全部在内存,通过排序将其有序。
外部排序指的是数据太大,无法一次性载入内存,采取的策略是:
- 将原始数据切分为k个块,保证每一块可以一次性载入内存完成排序
- 依次加载每一块到内存,完成排序,写入临时文件
- 维护一个最小堆,从k个文件各自取元素加入最小堆
- 从最小堆取堆顶写入最终文件,写入元素所在临时文件再填充一个新元素到最小堆
性能优化手段:
- 每个临时文件安排一个缓存,一次读一批
- 从堆取出先放入缓存,攒够一批一次性写入最终文件
转载自 CSDN-专业IT技术社区
原文链接:https://blog.csdn.net/x13262608581/article/details/170744224




