DS-07-03 交换排序

408 > ### 数据结构 > #### 交换排序（冒泡排序/快速排序）

---

一、定位信息

维度	内容
章节归属	第7章 排序
知识单元编号	DS-07-03
前置知识	DS-07-01 排序基本概念
后续衔接	DS-07-09 排序算法综合对比
考试大纲要求	掌握冒泡排序和快速排序的算法思想、实现、性能分析及改进
预计学习时长	50分钟

---

二、知识点讲解

1. 冒泡排序（Bubble Sort）

1.1 基本思想

冒泡排序的核心思想是相邻元素两两比较，将大的元素向后"冒泡"。每一趟从前往后依次比较相邻元素，若逆序则交换，一趟结束后最大的元素就"冒"到了末尾。

1.2 伪代码实现

void BubbleSort(ElementType A[], int n) {
    // 冒泡排序，A[0..n-1]
    int i, j;
    bool flag;  // 标记本趟是否发生交换
    for (i = 0; i < n - 1; i++) {  // 共需 n-1 趟
        flag = false;  // 每趟开始前重置标记
        for (j = 0; j < n - 1 - i; j++) {  // 每趟比较 n-1-i 次
            if (A[j].key > A[j+1].key) {    // 逆序则交换
                swap(A[j], A[j+1]);
                flag = true;  // 标记发生了交换
            }
        }
        if (flag == false)  // 本趟无交换，说明已有序
            break;          // 提前结束，这是优化后的版本
    }
}

1.3 时间复杂度分析

情况	条件	比较次数	交换次数	时间复杂度
最好	序列已有序	n-1	0	O(n)
最坏	序列逆序	n(n-1)/2	n(n-1)/2	O(n²)
平均	随机排列	n(n-1)/4	n(n-1)/4	O(n²)

最坏情况推导：第 i 趟比较 n-i-1 次（i=0,1,…,n-2），总比较次数 = (n-1)+(n-2)+…+1 = n(n-1)/2。

1.4 稳定性

稳定。因为只有当 A[j].key > A[j+1].key 时才交换，相同关键字不交换。

1.5 空间复杂度

O(1)，原地排序。

---

2. 快速排序（Quick Sort）

2.1 基本思想

快速排序是分治法在排序中的经典应用。其核心思想是：

1. 选基准：从待排序序列中选取一个元素作为基准（pivot）
2. 划分（Partition）：将序列分为两部分——左边所有元素 ≤ pivot，右边所有元素 ≥ pivot
3. 递归：对左右两部分分别递归执行快速排序

一趟划分后，基准元素已在最终正确位置。

2.2 伪代码实现

int Partition(ElementType A[], int low, int high) {
    // 一趟划分，选取 A[low] 为基准
    ElementType pivot = A[low];  // 将第一个元素作为基准
    while (low < high) {
        // 从右往左找第一个小于 pivot 的元素
        while (low < high && A[high].key >= pivot.key)
            high--;
        A[low] = A[high];  // 将其放到左边空位
        // 从左往右找第一个大于 pivot 的元素
        while (low < high && A[low].key <= pivot.key)
            low++;
        A[high] = A[low];  // 将其放到右边空位
    }
    A[low] = pivot;  // 基准元素放到最终位置
    return low;       // 返回基准的位置
}

void QuickSort(ElementType A[], int low, int high) {
    // 快速排序，对 A[low..high] 排序
    if (low < high) {
        int pivotpos = Partition(A, low, high);  // 一趟划分
        QuickSort(A, low, pivotpos - 1);   // 递归排左半部分
        QuickSort(A, pivotpos + 1, high);  // 递归排右半部分
    }
}

2.3 时间复杂度分析

最好情况：每次划分恰好将序列均分为两半。

• 递归树深度 = log₂n
• 每层划分的比较次数 = O(n)
• 总时间 = O(n log n)

最坏情况：每次划分都极不平衡（如序列已有序，选第一个为基准）。

• 递归树退化为链表，深度 = n
• 第 i 层比较 n-i 次
• 总比较次数 = n + (n-1) + … + 1 = n(n+1)/2
• 总时间 = O(n²)

平均情况：可以证明平均比较次数 ≈ 2n ln n ≈ 1.39n log₂n

• 总时间 = O(n log n)

情况	时间复杂度	空间复杂度（递归栈）	条件
最好	O(n log n)	O(log n)	每次划分均匀
最坏	O(n²)	O(n)	序列已有序/逆序
平均	O(n log n)	O(log n)	随机排列

2.4 稳定性

不稳定。划分过程中，与 pivot 相等的元素可能被交换到不同侧，改变相对顺序。

例如序列 [3, 3, 1]，选第一个 3 为 pivot，划分后两个 3 的相对顺序可能改变。

2.5 快速排序的优化

1. 随机选取基准：避免最坏情况
2. 三数取中法：取 A[low]、A[mid]、A[high] 三者的中位数作为 pivot
3. 小规模切换：当子序列长度小于阈值（如 10）时，改用直接插入排序
4. 尾递归优化：递归较短的一侧，迭代处理较长的一侧，减少栈深度

---

3. 冒泡排序 vs 快速排序 对比表

对比维度	冒泡排序	快速排序
基本思想	相邻比较交换，大元素冒泡	分治，划分基准
最好时间	O(n)	O(n log n)
最坏时间	O(n²)	O(n²)
平均时间	O(n²)	O(n log n)
空间复杂度	O(1)	O(log n) ~ O(n)
稳定性	稳定	不稳定
适用场景	n 较小或基本有序	通用，大规模数据首选
408 中地位	基础了解	重点中的重点

---

三、记忆辅助

1. 冒泡 = 相邻交换：像水中的气泡，大的一个一个往上冒
2. 快排 = 分治 + 划分：选基准 → 分左右 → 递归。是平均性能最好的内部排序
3. 快排最坏 = 已有序：选第一个为基准 + 已有序 = O(n²)，退化为冒泡
4. 快排不稳定的原因：划分过程中等于 pivot 的元素位置会变
5. 快排空间来自递归栈：不是辅助数组，是递归调用栈

---

四、例题精解

例题 1：快速排序的一趟划分过程

题目：对序列 (49, 38, 65, 97, 76, 13, 27, 49') 进行一趟快速排序（取第一个元素为基准），写出划分结果和基准的最终位置。

第一步：审题 使用上述 Partition 算法，以 A[0]=49 为基准，执行一趟划分。

第二步：逐过程模拟

初始：low=0, high=7, pivot=49 序列：[49, 38, 65, 97, 76, 13, 27, 49']

① 从右往左找 < 49 的元素：high 指向 27（下标 6） A[0] = A[6] → [27, 38, 65, 97, 76, 13, —, 49']

② 从左往右找 > 49 的元素：low 指向 65（下标 2） A[6] = A[2] → [27, 38, —, 97, 76, 13, 65, 49']

③ 从右往左找 < 49 的元素：high 指向 13（下标 5） A[2] = A[5] → [27, 38, 13, 97, 76, —, 65, 49']

④ 从左往右找 > 49 的元素：low 指向 97（下标 3） A[5] = A[3] → [27, 38, 13, —, 76, 97, 65, 49']

⑤ 从右往左找 < 49 的元素：high=low=3，循环结束 A[3] = pivot = 49 → [27, 38, 13, 49, 76, 97, 65, 49']

第三步：解答 一趟划分结果：[27, 38, 13, 49, 76, 97, 65, 49'] 基准 49 最终位于下标 3，左侧所有元素 ≤ 49，右侧所有元素 ≥ 49。

第四步：总结 一趟划分的时间复杂度为 O(n)，它是快排的基本操作。注意划分过程中 low 和 high 交替移动，最终 low == high 时即为基准的最终位置。

---

例题 2：快速排序的最坏情况分析

题目：对序列 (1, 2, 3, 4, 5, 6, 7, 8) 以第一个元素为基准进行快速排序，分析其时间复杂度。

第一步：审题 序列已有序，选第一个元素为基准，分析这种情况下的性能。

第二步：分析

每趟划分极度不平衡：

• 第 1 趟：pivot=1，左子序列为空，右子序列含 7 个元素，比较 7 次
• 第 2 趟：pivot=2，左子序列为空，右子序列含 6 个元素，比较 6 次
• …
• 第 7 趟：pivot=7，左子序列为空，右子序列含 1 个元素，比较 1 次

总比较次数 = 7+6+5+4+3+2+1 = 28 = 8×7/2

递归树退化为单支树，深度 = n = 8，每层比较次数递减。

第三步：解答 时间复杂度为 O(n²)，总比较次数 = n(n-1)/2 = 28 次。 这与冒泡排序的最坏情况完全一样，快速排序退化为"慢速排序"。

第四步：总结 这是快速排序的致命弱点。实际使用中必须采取优化措施：

1. 三数取中法选基准
2. 随机选取基准
3. 小规模子序列改用插入排序

---

例题 3：冒泡排序的提前终止

题目：对序列 (1, 2, 3, 8, 4, 5, 6, 7) 进行冒泡排序（带 flag 优化），需要几趟才能完成排序？

第一步：审题 使用带 flag 的冒泡排序，当一趟无交换时提前终止。

第二步：逐趟模拟

第 1 趟：比较相邻元素，发生交换（8 和 4 交换等） 结果：[1, 2, 3, 4, 5, 6, 7, 8]，flag = true

第 2 趟：无交换，flag = false，提前终止

第三步：解答 仅需 2 趟即可完成排序。

第四步：总结 带 flag 优化的冒泡排序在序列基本有序时可以达到 O(n) 的时间复杂度。这也是冒泡排序最好的时间复杂度。

---

五、考情分析

年份	题型	考点	难度
高频	分析题	快速排序的 Partition 过程	★★★
高频	选择题	快速排序的时间/空间复杂度	★★☆
中频	分析题	快速排序的最坏情况及优化	★★★
低频	选择题	冒泡排序的趟数	★★☆

命题趋势：

• 快速排序是408重点中的重点，几乎每年都有涉及
• Partition 过程的模拟是高频题型
• 最坏情况分析 + 优化策略是综合题的常见考点
• 冒泡排序相对简单，通常以选择题形式考查

---

六、易错点

1. Partition 中的比较方向：必须先从右往左找小的，再从左往右找大的。如果反过来，结果可能错误
2. 快排的递归终止条件：是 low < high，不是 low <= high。当 low == high 时只有一个元素，不需要排序
3. 快排不稳定的原因：不要误以为"相同元素不会动"，划分过程中与 pivot 相等的元素会被交换到不同侧
4. 冒泡排序的趟数：n 个元素最多需要 n-1 趟（不是 n 趟），因为 n-1 趟后最后一个元素自然到位
5. 快排空间复杂度：是 O(log n) ~ O(n)（递归栈），不是 O(1)。这与冒泡排序的 O(1) 不同
6. Partition 的内层循环条件：A[high].key >= pivot.key 包含等于的情况，否则等于 pivot 的元素会不断交换导致死循环

---

七、来源标注

• 《数据结构（C语言版）》严蔚敏，第10.3节 交换排序
• 《数据结构》王道考研，第7章 7.3节 交换排序
• 408考试大纲：数据结构部分-交换排序
• 《算法导论》Thomas H. Cormen，第7章 快速排序