Appearance
交换类排序
概念
交换类排序的基本动作是交换：通过反复交换逆序的元素对，把序列逐步调整成有序。
- 冒泡排序（bubble sort）：只交换相邻的两个元素，每趟把当前未排序部分的最大值"冒"到末尾。
- 快速排序（quick sort）：选一个枢轴（pivot），一趟划分（partition）把序列分成"全部 ≤ 枢轴"和"全部 ≥ 枢轴"两半，再对两半递归。
两者的本质区别在于交换的跨度：冒泡每次只让元素挪一位，快排一次划分就把元素扔到枢轴的另一侧——这个"一次解决一大片"的动作，就是快排平均性能碾压 O(n²) 类算法的原因。
一句话记忆：冒泡是"一趟只办一个元素的位"，快排是"一趟把序列劈成两半"。前者 O(n²)，后者平均 O(n log n)。
原理
一、冒泡排序
一趟的过程（升序）：
49 38 65 97 76 13 27 49*
↓ 38<49 交换
38 49 65 97 76 13 27 49*
↓ 65<49? 不换
38 49 65 97 76 13 27 49*
↓ 97>76 交换
...连比较带交换，一趟走到底，最大值 97 落到末尾每趟从左到右比较相邻两元素，逆序就换。走完一趟，当前未排序部分的最大值一定被推到末尾（这就是"冒泡"这个名字的由来）。
优化：设一个 exchange 标志。 若某一趟一次交换都没发生，说明序列已经有序，可以直接结束——这让冒泡在正序输入时做到 O(n)。
| 情况 | 比较次数 | 交换次数 | 时间 |
|---|---|---|---|
| 最好（正序，带标志） | 0 | O(n) | |
| 最坏（逆序） | O(n²) | ||
| 平均 | — | — | O(n²) |
空间 O(1)，稳定（只交换 a[j] > a[j+1] 的相邻对，相等不动）。
二、快速排序
1. 一趟划分（partition）—— 全部考点都在这里
取第一个元素为枢轴
① 挖坑：把 a[low] 存进 pivot，a[low] 视为"空坑"
[ 49 ] 38 65 97 76 13 27 49* pivot = 49, 坑在 low=1
② high 从右往左找 < pivot 的元素，挖出来填进左坑
27 38 65 97 76 13 [ 27 ] 49* 坑移到 high=7（原 27 的位置）
③ low 从左往右找 > pivot 的元素，挖出来填进右坑
27 38 [ 65 ] 97 76 13 65 49* 坑移到 low=3
④ 重复 ②③ 直到 low >= high
27 38 13 97 76 [ 97 ] 65 49* 坑移到 high=5
27 38 13 [ 97 ] 76 97 65 49* 坑移到 low=4
⑤ 把 pivot 填进最后的坑
27 38 13 49 76 97 65 49* 枢轴归位，low=high=4一趟划分结束时，枢轴已经落在它最终有序位置，这是快排的核心不变量：每次划分都至少有 1 个元素永久归位。
2. 递归结构
[49 38 65 97 76 13 27 49*]
↓ 划分，枢轴 49 归位到下标 4
左半 [27 38 13] | [76 97 65 49*] 右半
↓ 枢轴 27 ↓ 枢轴 76
[13] | [38] [49* 65] | [97]
↓ ↓ 枢轴 49*
空 空 [] | [65]本例最大递归深度 3（层数从 1 数起）。
3. 复杂度
| 情况 | 触发条件 | 时间 | 递归深度 |
|---|---|---|---|
| 最好 | 每次划分都近似均分两半 | ||
| 平均 | 随机数据 | ||
| 最坏 | 序列已正序或已逆序（枢轴取首元素时每次都分出 0 个） |
空间复杂度就是递归栈的深度：平均
最好情况的公式推导：
最坏情况是每次只把一个元素分离出去：
快排为什么"平均最快"：虽然平均与归并同为 O(n log n)，但快排的内层循环只是一次比较 + 一次自增，常数极小，且顺序访问数组对 CPU 缓存（cache）友好。所以在实际运行中它通常比归并、堆排序都快。缺点是不稳定、最坏 O(n²)。
示例
统一使用序列 49, 38, 65, 97, 76, 13, 27, 49*。
例 1：冒泡排序逐趟推演
| 趟次 | 本趟比较次数 | 本趟交换 | 结果 |
|---|---|---|---|
| 初始 | — | — | 49 38 65 97 76 13 27 49* |
| 1 | 7 | 5 | 38 49 65 76 13 27 49* 97 |
| 2 | 6 | 4 | 38 49 65 13 27 49* 76 97 |
| 3 | 5 | 4 | 38 49 13 27 49* 65 76 97 |
| 4 | 4 | 2 | 38 13 27 49 49* 65 76 97 |
| 5 | 3 | 1 | 13 27 38 49 49* 65 76 97 |
| 6 | 2 | 0 | 13 27 38 49 49* 65 76 97（无交换 → 结束） |
统计：共进行 6 趟（第 5 趟已排好，第 6 趟只是"检查后退出"），比较 27 次、交换 15 次。
对比最坏情况：逆序时需
次比较、同样 28 次交换。本例只省了 1 次比较，却省了 13 次交换——交换次数才是冒泡的性能瓶颈。
例 2：快速排序一趟划分的完整手算
以
49为枢轴，写出序列49, 38, 65, 97, 76, 13, 27, 49*一趟划分的每一步。
| 步骤 | 动作 | low | high | 序列 |
|---|---|---|---|---|
| 初始 | 取 a[1]=49 存为 pivot，a[1] 成坑 | 1 | 8 | [●] 38 65 97 76 13 27 49* |
| ① | high 左移：49* ≥ 49 → 跳过；27 < 49 → 填入左坑 | 2 | 7 | 27 38 65 97 76 13 [●] 49* |
| ② | low 右移：38 < 49 → 跳过；65 > 49 → 填入右坑 | 3 | 6 | 27 38 [●] 97 76 13 65 49* |
| ③ | high 左移：13 < 49 → 填入左坑 | 4 | 5 | 27 38 13 97 76 [●] 65 49* |
| ④ | low 右移：97 > 49 → 填入右坑 | 4 | 4 | 27 38 13 [●] 76 97 65 49* |
| ⑤ | low = high，pivot 落位 | 4 | 4 | 27 38 13 49 76 97 65 49* |
结果：27 38 13 [49] 76 97 65 49*，枢轴 49 归位到下标 4，左半全部 < 49，右半全部 ≥ 49。
注意右半里的
49*被判为"≥ 枢轴"留在了右侧，而左半的27, 38, 13都被换到了左边。这一步之后，49与49*的相对次序还看不出来，但继续递归下去后49*会排到49前面（见下文稳定性分析）。
例 3：递归展开与最终序列
第一步，划分 [49 38 65 97 76 13 27 49*] → [27 38 13] 49 [76 97 65 49*]
第二步，处理左半 [27 38 13]：枢轴 27 → [13] 27 [38]
第三步，处理右半 [76 97 65 49*]：枢轴 76 → [49* 65] 76 [97]
第四步，处理 [49* 65]：枢轴 49* → [] 49* [65]
第五步，递归结束，最终序列：
13 27 38 49 49* 65 76 97关键观察：本例中 49 与 49* 恰好保持了原有次序——因为 49 从头到尾都是枢轴，一直待在左边，49* 一直待在右边，两者从未跨侧交换。但这只是这组数据的巧合，不能推出快排稳定。
要看到快排真正的不稳定，需要一个"相等元素被迫跨侧"的例子：
序列
2A, 2B, 1，取首元素为枢轴。 划分时high从右往左找到1 < 2A，把它填进左侧的坑，于是2A被挪到下标 3 的坑里：[2A] 2B 1 → 1 [2B] 2A一趟划分后
2A就排到了2B后面，排序结果为1, 2B, 2A——不稳定。
原因：划分对 high 指针是从右往左找小元素，找到后要把它送到左侧。这一送是长距离的，会让某个元素越过它的"同值伙伴"。远距离搬运 = 不稳定，这与简单选择排序不稳定的根源完全一样。
C 语言：冒泡排序与快速排序
#include <stdio.h>
/* ---------- 冒泡排序（升序，带提前退出标志） ---------- */
void bubbleSort(int a[], int n) {
for (int t = 0; t < n - 1; t++) {
int swapped = 0;
for (int j = 0; j < n - 1 - t; j++) {
if (a[j] > a[j + 1]) { /* 只有严格逆序才换，保证稳定 */
int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x;
swapped = 1;
}
}
if (!swapped) break; /* 本趟无交换：已有序 */
}
}
/* ---------- 一趟划分（挖坑填数法，枢轴取首元素） ----------
返回枢轴最终所在下标。划分结束时 pivot 已永久归位。 */
int partition(int a[], int low, int high) {
int pivot = a[low]; /* 挖坑：a[low] 成空位 */
while (low < high) {
while (low < high && a[high] >= pivot) high--; /* 从右找工作 < pivot */
if (low < high) { a[low] = a[high]; low++; }
while (low < high && a[low] <= pivot) low++; /* 从左找工作 > pivot */
if (low < high) { a[high] = a[low]; high--; }
}
a[low] = pivot; /* pivot 落进最后的坑 */
return low;
}
void quickSort(int a[], int low, int high) {
if (low < high) { /* 长度 <= 1 直接返回 */
int p = partition(a, low, high);
quickSort(a, low, p - 1); /* 两半递归 */
quickSort(a, p + 1, high);
}
}
int main(void) {
int b[8] = {49, 38, 65, 97, 76, 13, 27, 49};
int q[8] = {49, 38, 65, 97, 76, 13, 27, 49};
bubbleSort(b, 8);
quickSort(q, 0, 7);
printf("冒泡: "); for (int i = 0; i < 8; i++) printf("%d ", b[i]); printf("\n");
printf("快排: "); for (int i = 0; i < 8; i++) printf("%d ", q[i]); printf("\n");
/* 两者都是：13 27 38 49 49 65 76 97
本例两个 49 恰好保持原次序 —— 但快排并不稳定，反例见 Python 对照 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
想直接看出快排的不稳定，用一个短序列就够了：
[2, 2, 1]（取首元素为枢轴）排序后两个2的次序会颠倒。下文 Python 对照里用带标记的二元组把这个现象打出来。
Python 对照
def bubble_sort(a):
a = a[:]
n = len(a)
for t in range(n - 1):
swapped = False
for j in range(n - 1 - t):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return a
def partition(a, low, high):
pivot = a[low]
while low < high:
while low < high and a[high] >= pivot:
high -= 1
if low < high:
a[low] = a[high]; low += 1
while low < high and a[low] <= pivot:
low += 1
if low < high:
a[high] = a[low]; high -= 1
a[low] = pivot
return low
def quick_sort(a):
a = a[:] # 拷贝一份，不动原列表
def qs(low, high):
if low < high:
p = partition(a, low, high)
qs(low, p - 1) # 左半
qs(p + 1, high) # 右半
qs(0, len(a) - 1)
return a
src = [49, 38, 65, 97, 76, 13, 27, 49]
print("冒泡:", bubble_sort(src))
print("快排:", quick_sort(src))
# —— 用带标记的元组观察稳定性（注意：比较只看第 0 个字段）——
def partition_tagged(a, low, high):
pivot = a[low]
while low < high:
while low < high and a[high][0] >= pivot[0]: high -= 1
if low < high: a[low] = a[high]; low += 1
while low < high and a[low][0] <= pivot[0]: low += 1
if low < high: a[high] = a[low]; high -= 1
a[low] = pivot
return low
def qs_tagged(a, low, high):
if low < high:
p = partition_tagged(a, low, high)
qs_tagged(a, low, p - 1)
qs_tagged(a, p + 1, high)
# 反例：2A 与 2B 相等，快排后 B 跑到 A 前面 → 不稳定
t = [(2, 'A'), (2, 'B'), (1, '')]
qs_tagged(t, 0, len(t) - 1)
print("快排 [2A,2B,1] ->", t) # [(1,''), (2,'B'), (2,'A')]
print("sorted 【Timsort，稳定】->", sorted([(2,'A'),(2,'B'),(1,'')]))
print("sorted key=第0字段 ->", sorted([(2,'A'),(2,'B'),(1,'')], key=lambda x: x[0]))
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n)（带标志，正序） | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | 平均 O(log n)，最坏 O(n) | 不稳定 |
- 冒泡最坏比较次数与交换次数都是
- 快排最坏出现在序列已正序或已逆序（枢轴固定取首元素时），此时递归深度
- 快排的空间复杂度 = 递归栈深度，不是 O(1)。
- 快排每趟划分至少确定一个元素的最终位置；一趟划分后枢轴左边的都 ≤ 它，右边都 ≥ 它。
2. 手算套路
- 一趟划分：画两行——上面是数组，下面是
low/high指针。永远记住"反向指针找元素填对面那个坑"，比背代码快。 - 递归展开：把每层划分后的枢轴及其下标单独抄一行，最后按下标把各层的枢轴拼起来就是有序序列（不用把每层的完整数组都画出来）。
- 求第 k 趟（第 k 层）结果：只画前 k 层。
3. 易错点
- 快排一开始就有元素归位，但一轮归位的只是枢轴本身：不要说成"一趟就排好了一半元素"。
- 快排不稳定：划分时 high 指针是"从右往左找小元素，然后把它长距离送到左侧"，这一步会让元素越过同值伙伴。最小反例：
2A, 2B, 1→ 排序后2B跑到了2A前面。注意：不要用"有序的 49, 49*"这类例子去证明快排不稳定——若相等元素恰好从头到尾都在枢轴同侧，反而会保持次序。举反例必须让相等元素被迫跨侧。
- 快排的最坏情况判断依据是"枢轴选取方式"，不是数据量。取首元素为枢轴时，正序反而最慢；取中位数（三数取中）或随机枢轴可以规避。补充："快排最坏是 O(n²)"是考点，"用三数取中可使最坏也接近 O(n log n)"是常识扩展。
- 快排比归并/堆排序快，不是因为渐进复杂度更好（都是 O(n log n)），而是因为常数因子小、缓存友好。题目说"快排平均性能最好"时，问的是实际运行时间，不是渐进阶。
- "枢轴值相同的元素"处理：判断条件写
>=或>对最终结果与稳定性的影响不同，也影响最坏情况（序列全是同一个值时的退化）。看一下题目给的代码。 - 递归次数 vs 递归深度：一趟划分会把问题分成左右两半，递归调用总次数 ≈ 枢轴个数 = n，但栈的最大深度是层数，两者别混。递归次数是 O(n)，栈深是 O(log n) ~ O(n)。
- 冒泡的第 n−1 趟要不要算：带标志的实现里，若某趟无交换会提前结束，所以实际趟数可能小于
小结
- 交换类排序靠交换逆序对推进：冒泡只换相邻，快排一次划分跨两侧。
- 冒泡：稳定、O(1) 空间、最好 O(n)（带标志）、最坏与平均 O(n²)；交换次数是它真正的代价。
- 快排：一趟划分让枢轴永久归位，平均 O(n log n)、最坏 O(n²)、不稳定、栈深 O(log n)~O(n)。
- 快排的功夫全在枢轴选取上：固定取首元素最怕有序输入，工程上要用三数取中或随机化。
- 至此，"靠比较并把元素挪来挪去"的两条路线（插入、交换）都讲完了。下一步换第三种思路：一趟只选出一个最值，不做多余交换。
- 补充一句：快速排序是 408 中与归并、堆并列的三大 O(n log n) 算法之一，三者的对比表在 43 篇统一给出。
下一篇：选择类排序：简单选择、堆排序
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。