一、冒泡排序#

1. 核心原理：通过重复遍历待排序序列，依次比较相邻两个元素的大小，若顺序错误则交换它们，每一轮遍历都会将当前未排序序列中的最大（或最小）元素“冒泡”到末尾的正确位置。
2. 考研核心考点
   • 时间复杂度：未优化版本下，最坏/平均情况为$O(n^2)$，最优情况（序列已有序）下，通过设置交换标记优化后可降至$O(n)$；
   • 空间复杂度：仅使用常数级额外空间，为$O(1)$；
   • 稳定性：属于稳定排序算法，相等元素的相对位置不会因交换发生改变；
   • 适用场景：小规模、近乎有序的序列，实现简单但整体效率较低。
3. 常见优化：通过设置flag标记本轮遍历是否发生交换，若未交换则说明序列已有序，可直接提前终止循环。

二、快速排序#

1. 核心原理：基于分治思想的排序算法，核心步骤为分区（Partition）：
   1. 选取一个基准元素（Pivot）；
   2. 将序列划分为两部分，左侧所有元素小于等于基准，右侧所有元素大于等于基准，基准元素处于最终的正确位置；
   3. 递归对左右两个子序列重复上述步骤，直至所有子序列长度为1。
2. 考研核心考点
   • 时间复杂度：最优/平均情况为$O(n\log n)$（每次分区都能将序列均匀划分为两个等长子序列），最坏情况（如有序序列选取首元素作为基准）为$O(n^2)$；
   • 空间复杂度：最优情况为$O(\log n)$（递归栈深度为$\log_2 n$），最坏情况为$O(n)$；
   • 稳定性：属于不稳定排序算法，跨元素交换可能会改变相等元素的相对位置；
   • 常见优化：三数取中法选取基准、随机选取基准避免最坏情况、当子序列长度较小时改用插入排序减少递归开销；
   • 分区实现：常考察Hoare分区（双指针法）与Lomuto分区（单指针法）两种经典实现方式。

三、考点对比#

结合408选择题高频考点，对比冒泡排序与快速排序的核心差异：