核心思想#

• 相邻比较：每次比较相邻的两个元素，如果逆序则交换
• 逐趟冒泡：每一趟都将当前未排序部分的最大元素”冒泡”到末尾
• 提前终止：若某一趟没有发生任何交换，说明序列已有序，可直接结束

代码实现（带提前终止优化）#

1
void BubbleSort(int a[], int n) {
2
    for (int i = 0; i < n - 1; i++) {
3
        bool swapped = false;
4
        for (int j = 0; j < n - 1 - i; j++) {
5
            if (a[j] > a[j + 1]) {
6
                int tmp = a[j];
7
                a[j] = a[j + 1];
8
                a[j + 1] = tmp;
9
                swapped = true;
10
            }
11
        }
12
        if (!swapped) break;   // 本趟无交换，提前终止
13
    }
14
}

复杂度#

⚠️ 易错：冒泡排序的最好情况是 O(n)，前提是代码中有提前终止优化。

核心思想#

快排是排序章节考频最高的算法。核心是分治法：

• 分区：选一个元素作为基准（pivot），将序列划分为两部分——左边 ≤ pivot，右边 ≥ pivot
• 递归：对左右子序列分别递归执行快速排序
• 合并：无需合并，分区完成后序列自然有序

Partition 过程（⭐ 必考手写）#

以第一个元素为 pivot，双指针从两端向中间扫描：

1
int Partition(int A[], int low, int high) {
2
    int pivot = A[low];
3
    while (low < high) {
4
        while (low < high && A[high] >= pivot) high--;
5
        A[low] = A[high];
6
        while (low < high && A[low] <= pivot) low++;
7
        A[high] = A[low];
8
    }
9
    A[low] = pivot;
10
    return low;
11
}
12

13
void QuickSort(int A[], int low, int high) {
14
    if (low < high) {
15
        int pivotPos = Partition(A, low, high);
16
        QuickSort(A, low, pivotPos - 1);
17
        QuickSort(A, pivotPos + 1, high);
18
    }
19
}

⚠️ 易错：Partition 中 while 条件的 >= 和 <= 不能改成 > 和 <，否则与 pivot 相等时会死循环。

递归分析#

• 最好情况：每次 pivot 将序列等分，递归树平衡，树高 log₂n → O(n log n)
• 最坏情况：每次 pivot 是最小/最大值，递归树退化为单链，树高 n → O(n²)

复杂度#

pivot 优化策略#

1. 随机选取 pivot：从子序列中随机选一个与 A[low] 交换
2. 三数取中法：取 A[low]、A[mid]、A[high] 的中值作为 pivot
3. 子序列短时改用插入排序

最坏情况#

最坏情况发生在序列基本有序（正序或逆序）+ 取首元素为 pivot 时：

• 每趟只能确定一个元素的位置，需 n-1 趟
• 比较次数：n(n-1)/2 = O(n²)

⚠️ 易错：快排 O(n²) 不意味着快排不好。408 常考”对任意输入数据，以下哪种最坏仍为 O(n log n)？“——答案是归并和堆排。

冒泡排序#

• ⭐ 每趟结果（选择题/填空题）
• ⭐ 提前终止优化的条件与最好 O(n)
• ⭐ 比较次数与交换次数计算

快速排序#

• ⭐ ⭐ 手动模拟 Partition 过程（选择题/填空题必考）
• ⭐ 时间复杂度（最好/最坏/平均）
• ⭐ 最坏情况发生条件（有序 + 首元素 pivot）
• ⭐ 每趟至少确定一个元素的最终位置
• ⭐ 不稳定排序的反例
• pivot 优化策略
• 快排 vs 归并 vs 堆排的综合对比