好的算法不是把每一步做得更快，而是让每一步消灭掉更多问题。
冒泡排序
想象一排身高不同的人站成一队，你要把他们从矮到高排好。规则很简单：每次只能比较相邻两个人，如果左边比右边高，就让他们交换位置。从队伍最左边开始，一路比较到最右边，走一轮下来，最高的那个人肯定会被“冒泡”到最右端。不知道为什么起这么抽象的名字———冒泡排序。泡泡排序最后冒出来？
假设有一数组：[5, 2, 9, 1, 5]
第一轮：
比较5和2-> 5>2，交换 -> [2, 5, 9, 1, 5]
比较5和9-> 不用交换 -> [2, 5, 9, 1, 5]
比较9和1-> 9>1，交换 -> [2, 5, 1, 9, 5]
比较9和5-> 9>5，交换 -> [2, 5, 1, 5, 9]
一轮下来，最大的数字9已经排到了最右边。
第二轮（不用再管最后一位了)：
继续从头比较，把第二大的数字送到倒数第二位 以此类推，每一轮都能确定一个数字的最终位置，直到整个数组有序。
C++实现冒泡排序
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
快速排序
选一个基准值，把数组分成两部分：比基准小的放左边，比基准大的放右边。然后对左右两部分递归地重复这个过程，直到每部分只剩一个元素。
假设有：[5, 2, 9, 1, 5, 6]，选最后一个元素 6 作为基准
用一个指针 i 记录"小于基准区域"的边界，遍历数组，凡是小于基准的元素就交换到左边
[5, 2, 9, 1, 5, 6] 基准 = 6
所有元素都 < 6，所以整个数组不变
分区后：[5, 2, 9, 1, 5] | 6
这一轮下来，6已经在它最终该在的位置上（因为左边全部比它小）。
递归处理左右两部分，直到每部分长度为 1 或 0。
C++实现快速排序
int partition(std::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) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}快排如果总是找最后一个做为基准，那么最坏情况下就是碰到有序数组：[1,2,3,4,5,6] 这样就需要O(n²),我们需要避免这种情况。
有两种策略避免快排最坏情况：随机选择基准、取中位数。
为什么快速排序比冒泡排序更快？
快速排序比冒泡排序快的核心原因在于问题规模缩减的方式不同：冒泡排序每一轮遍历只能确定一个元素的最终位置，相当于每次让问题规模减少 1，n 个元素需要大约 n 轮、每轮 O(n) 次比较，总复杂度是 O(n²)；而快速排序每次分区操作虽然也需要 O(n) 的开销，但能一次性把数组对半分（确定基准值位置后递归处理两个子问题），这种指数级缩减规模的方式使得递归深度只有 O(log n) 层，每层总工作量都是 O(n)，因此总复杂度是 O(n log n)——本质上就是每次减半（log n）比每次减一（n）快得多，这也是分治算法相比线性遍历类算法的普遍优势所在。