Lecture 31：交换排序

交换排序通过交换记录位置消除逆序。冒泡排序只交换相邻逆序对，直观且稳定；快速排序通过一次划分将枢轴放到最终位置，平均性能优异，但枢轴选择不当会退化。

31.1 冒泡排序

31.1.1 一趟冒泡

定义：#冒泡排序

描述：相邻元素两两比较，若为逆序则交换。一趟处理后，一个极值元素会移动到未排序区边界。

• 若内层从右向左扫描，第一趟把最小元素移动到最前面；若从左向右扫描，第一趟把最大元素移动到最后面。两种方向本质相同。
• 已确定最终位置的一端不必在后续趟中再次参加比较。
• 只在严格逆序 A[j-1] > A[j] 时交换，相等关键字不会互换，因此冒泡排序稳定。

void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int changed = 0; // 0 表示本趟尚未交换
        for (int j = n - 1; j > i; --j)
            if (A[j - 1] > A[j]) {
                int t = A[j - 1];
                A[j - 1] = A[j];
                A[j] = t;
                changed = 1;
            }
        if (!changed) return; // 本趟无交换，表已整体有序
    }
}

31.1.2 性能

• 最好情况：原表有序，带 changed 标志时只需一趟，时间为 $O(n)$。
• 最坏情况执行全部 $n-1$ 趟，关键字比较次数为：

$$ \frac{n(n-1)}{2}=O(n^2) $$

• 对带 changed 提前结束的实现，平均比较次数依输入分布而变，量级仍为 $\Theta(n^2)$，不能把平均情况的精确比较次数也写死为 $n(n-1)/2$。若实现无提前结束，比较次数才对所有输入固定为该值。
• 辅助空间为 $O(1)$；可在链表上通过交换结点内容或调整链接实现。
• 若代码没有“本趟无交换即结束”的优化，即使原表有序也会执行全部趟，最好时间不再是 $O(n)$。

---

31.2 快速排序

31.2.1 划分思想

定义：#快速排序 #枢轴 #划分

描述：从待排序区选择一个枢轴（pivot），经一次划分使枢轴左边关键字均不大于它、右边关键字均不小于它；枢轴因此位于最终位置。再递归处理左右子表。

int Partition(int A[], int low, int high) {
    int pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot) --high;
        A[low] = A[high];
        while (low < high && A[low] <= pivot) ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int p = Partition(A, low, high);
        QuickSort(A, low, p - 1);
        QuickSort(A, p + 1, high);
    }
}

划分结束后必须成立：

$$ A[low\ldots p-1]\le A[p]\le A[p+1\ldots high] $$

• 枢轴仅在本次区间内到达最终位置；递归处理前不能认为其左右子表已经内部有序。
• 双指针填坑法中，先从右找小于枢轴者填到左侧，再从左找大于枢轴者填到右侧，最终把暂存的枢轴填回交汇位置。
• 递归终止条件为区间元素数不超过一个，即 low >= high。

对 $49,38,65,97,76,13,27,49$ 取首元素 $49$ 为枢轴，一趟划分可得到 $27,38,13,49,76,97,65,49$。只有绿色枢轴 $49$ 的最终位置已经确定，左右两段各自仍未有序；等于枢轴的另一个 $49$ 留在右段也符合本实现的边界条件。

31.2.2 复杂度与枢轴选择

• 若每次枢轴近似将区间均分，递归树高度为 $O(\log n)$，每层划分总工作量为 $O(n)$：

$$ T(n)=O(n\log n) $$

• 若每次枢轴恰为最小或最大元素，例如对已近有序表始终取首元素，递归深度为 $n$，最坏时间为 $O(n^2)$。
• 递归栈空间平均为 $O(\log n)$，最坏为 $O(n)$；不要把递归空间误写成 $O(n^2)$。
• 快速排序不稳定：划分中的远距离移动可能改变相等关键字记录的次序。
• 为降低退化概率，可随机选枢轴或取首、中、尾三者的中值；这改善实际表现，但不能消除最坏 $O(n^2)$ 的可能。

每个内部结点表示一次划分后到达最终位置的枢轴。树越接近完全二叉树，递归越浅；若不断形成单支链，就会退化为最坏情况。

题型：#快速排序划分判断

第一部分：解题方法

1. 记录本趟枢轴及初始 low、high，严格按题目给定的划分代码移动指针。
2. 一次划分结束后，只有枢轴的位置可确定；左右区域还需递归。
3. 判断某元素“可能是枢轴”时，检查它左侧是否全不大于它、右侧是否全不小于它；满足只是必要的排列特征，仍要结合具体划分过程。

第二部分：2019 统考真题

“对尚未确定最终位置的所有元素进行一遍处理称为一趟”，下列序列不可能是快速排序第二趟结果的是：

答案为 D。判断方法不是看序列是否已经整体有序，而是找“左侧全小于它、右侧全大于它”的已归位枢轴：

• A 可先以 $72$ 划分，再以 $28$ 划分左段。
• B 可先以 $2$ 划分，再以 $72$ 划分右段。
• C 可先以 $28$ 划分，第二趟分别用 $2$ 和 $32$ 划分左右段。
• D 的归位候选只有 $12$ 和 $32$。若第一趟枢轴是 $12$，第二趟处理左侧二元段后不可能仍为 $5,2$；若第一趟枢轴是 $32$，第二趟处理右侧二元段后不可能仍为 $72,60$，故不存在合法的两趟划分树。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：插入排序 · 下一篇：选择排序
• 关联专题：排序代码

31.3 本节复盘

• 冒泡排序相邻交换、稳定、原地；带标志时有序表最好 $O(n)$，一般为 $O(n^2)$。
• 快速排序一次划分确定一个枢轴最终位置；平均 $O(n\log n)$，最坏 $O(n^2)$。
• 快排性能取决于划分是否均衡，稳定性和最坏递归深度是高频考点。