考研笔记

交换排序

快速排序是本章分值最高的一节，而它最容易失分的地方，是「教材版的 Partition 只有一种」。

算法竞赛里 Hoare、Lomuto、三路划分随便挑，只要复杂度对就行。408 问「第一趟划分后的序列」时答案是唯一的——必须按教材那一版走。这一节的重心因此不在思想，而在手上的那套固定动作。

机制

冒泡排序

从后往前（或从前往后）两两比较相邻元素的值，若为逆序则交换，直到序列比较完。称这样过程为一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或最大的到最后一个位置）。

每一趟冒泡都能确定一个元素的最终位置。

指标值
最好时间（表已正序，一趟就发现没有交换）
平均 / 最坏时间
空间
稳定性稳定（相等时不交换）
适用存储顺序 + 链式

边界辨析：

冒泡排序的最好情况是 ，前提是算法里有「本趟无交换则提前结束」的判断。 没有这个判断的版本最好情况也是 。教材的表 8.1 给的是 ，说明默认带这个优化。 与之对照，简单选择排序 的最好情况也是 ， 因为它与序列的初始状态无关——这是两者最常被放在一起考的差别。

快速排序：教材版的 Partition

基于分治法：在待排序表 中任取一个元素 pivot 作为枢轴，通过一趟排序将待排序表划分为独立的两部分 和 ，使得 中的所有元素小于 pivot， 中的所有元素大于或等于 pivot，则 pivot 放在了其最终位置 上，这个过程称为一次划分。然后分别递归地对两个子表重复上述过程。

教材的 Partition 是「先从前往后，再从后往前」的双指针填坑法：

int Partition(ElemType K[],int n){
    //交换序列 K[1..n] 中的记录，使枢轴到位，并返回其所在位置
    int i=1,j=n;                    //设置两个交替变量初值分别为 1 和 n
    ElemType pivot=K[j];            //枢轴
    while(i<j){                     //循环跳出条件
        while(i<j&&K[i]<=pivot)
            i++;                    //从前往后找比枢轴大的元素
        if(i<j)
            K[j]=K[i];              //移动到右端
        while(i<j&&K[j]>=pivot)
            j--;                    //从后往前找比枢轴小的元素
        if(i<j)
            K[i]=K[j];              //移动到左端
    }   //while
    K[i]=pivot;                     //枢轴存放在最终位置
    return i;                       //返回存放枢轴的位置
}

口径差异：

这一版有三个必须照抄的细节，任何一个换成算竞习惯都会得到不同的中间序列：

细节教材常见算竞写法
枢轴取谁pivot = K[j]，即最后一个元素（Partition(K,1,n) 时是 ）常取中间元素或随机
移动方式填坑（K[j]=K[i] 覆盖），全程只有一个空位常用 swap 对撞
先动哪一头先 i++ 从前往后，再 j-- 从后往前常先从右往左
等号归谁K[i]<=pivot 前进、K[j]>=pivot 后退，等号两边都停不下来各种写法都有

题目问「第一趟划分后的序列」，只有按这四条走才对得上标准答案。

性能：

指标值
最好 / 平均时间
最坏时间（每次划分极不平衡，如已有序）
空间（递归工作栈），最坏
稳定性不稳定
适用存储仅顺序存储

教材原话：「快速排序基于分治的思想，虽然最坏情况下的时间复杂度会达到 ，但快速排序的平均性能可以达到 ，在实际应用中常常优于其他排序算法。」 8.6.2 进一步说：「当待排序的关键字随机分布时，快速排序被认为是目前基于比较的内部排序算法中最好的算法。」

边界辨析：

快速排序的空间复杂度不是 。 它需要借助一个递归工作栈，平均大小为 ， 最坏情况下可能会增长到 。 这是表 8.1 里唯一一个「时间快但空间不是 」的原地排序——堆排序才是 ， 所以 8.6.2 说「堆排序所需的辅助空间少于快速排序」。

每趟的效果：快速排序一趟处理至少能确定一个元素的最终位置（枢轴）。这句话是「根据中间过程判断所采用的排序算法」这类题的核心判据。

手算模板

冒泡排序第 趟后：从后往前冒泡时，前 个位置已是最终位置（最小的 个已就位）。

快速排序一趟划分（教材版，区间 ）：

  1. pivot = K[high]，i=low，j=high。
  2. i 向右走，直到 K[i] > pivot 或 i==j；把 K[i] 填到 K[j]。
  3. j 向左走，直到 K[j] < pivot 或 i==j；把 K[j] 填到 K[i]。
  4. 回到第 2 步，直到 i==j。
  5. K[i]=pivot，返回 i。

验算：划分后 K[i] 左边全 枢轴、右边全 枢轴，且枢轴已在最终位置。

判断中间序列是哪种算法：

现象算法
每趟后最大（或最小）的若干个已在两端就位冒泡 / 简单选择 / 堆排序
每趟后至少一个元素在最终位置，但位置不固定快速排序
每趟后前若干个有序但不一定在最终位置直接插入排序
相隔固定距离的元素成对有序希尔排序

边界

说法判断说明
「冒泡排序最好情况 」❌带提前结束判断时为
「冒泡排序不稳定」❌稳定（相等不交换）
「快速排序的空间复杂度是 」❌，最坏 ，因为有递归工作栈
「快速排序稳定」❌不稳定
「快速排序最坏 」❌最坏 ，如序列已有序
「快速排序对有序序列最快」❌正相反，此时划分最不平衡
「快速排序可用于链表」❌仅顺序存储
「一趟快排后所有元素都到最终位置」❌至少一个（枢轴）到最终位置
「枢轴可以随便取，结果一样」⚠️复杂度量级一样，但中间序列不同，考试按教材版
「快排是最好的排序算法」⚠️限定语是**「当待排序的关键字随机分布时，基于比较的内部排序算法中」**

对照速查

算法最好平均最坏空间稳定存储
冒泡是顺序 + 链式
快速否仅顺序
教材版 Partition 的四条内容
枢轴K[j]，区间最后一个元素
移动填坑（赋值覆盖），不是 swap
顺序先 i 向右，再 j 向左
等号<= 前进、>= 后退

考点

  • 教材版 Partition 的一趟结果——中间序列唯一，必须照教材走。
  • 快速排序的空间复杂度是 ，最坏 。
  • 快速排序最坏情况出现在序列已有序时。
  • 快排一趟至少确定一个元素的最终位置（2012 命题追踪）。
  • 根据排序的中间过程判断所采用的排序算法（2009、2010 命题追踪）。
  • 冒泡稳定、快排不稳定。
  • 冒泡最好 vs 简单选择恒为 。

链接

反向链接