快速排序：如何选择基准？分区过程图解¶
一、快速排序是什么？¶
快速排序是一种经典的排序算法，它基于 分治法 的思想：先将一个大问题分解成多个小问题，逐个解决后合并结果。核心步骤是 选一个基准（pivot），然后把数组分成两部分——左边都小于基准，右边都大于基准，再递归排序左右两部分。
快速排序的优势是 平均效率极高（平均时间复杂度 O(n log n)），但如果基准选择不当，可能退化为 O(n²)，所以“基准选择”和“分区过程”是快速排序的关键。
二、基准（pivot）怎么选？¶
基准是快速排序的“导航灯”，选得好，分区更平衡，排序更快；选得差，可能导致数组“一边倒”，效率暴跌。常见的基准选择方法有以下几种：
1. 最左/最右元素（最简单但易踩坑）¶
直接选数组第一个或最后一个元素作为基准。
- 缺点：若数组已排序（如 [1,2,3,4,5]），选最左元素（1）会导致分区后左边为空，右边全是大于1的元素，此时每轮分区都只处理 n-1 个元素，时间复杂度退化为 O(n²)。
- 例子：数组 [1,2,3,4,5]，选基准 1 → 分区后右边是 [2,3,4,5]，递归处理 [2,3,4,5] 同理，最终时间复杂度 O(n²)。
2. 中间元素（避免极端情况）¶
选数组中间位置的元素作为基准，比如长度为 n 的数组，基准索引为 n//2。
- 优点：比最左/最右更平衡，减少极端情况概率。
- 缺点：若数组接近有序，中间元素仍可能导致分区不平衡（如 [1,3,5,7,9]，中间元素 5 分区后左边 [1,3]，右边 [7,9]，递归处理没问题，但极端情况仍可能出问题）。
3. 三数取中法（最推荐）¶
取数组 首、尾、中间三个元素的中值 作为基准，既能避免有序数组的退化，又能保证分区平衡。
- 例子：数组 [1,2,3,4,5]，首=1，尾=5，中间=3，中值是 3 → 分区后左边 [1,2]，右边 [4,5]，递归处理更高效。
- 优势：几乎不会出现分区不平衡，时间复杂度稳定在 O(n log n)。
三、分区过程：把数组“一分为二”¶
分区（Partition）是快速排序的核心步骤，目标是让基准归位，并将数组分为“左小右大”两部分。这里用 左右指针法 演示分区过程，以数组 [5,3,8,4,2,7,1,6] 为例（假设基准选最左元素 5）：
步骤 1：初始化¶
数组：[5,3,8,4,2,7,1,6]，基准 pivot = 5（左指针 i=0，右指针 j=7，i 和 j 分别指向数组两端）。
步骤 2：移动右指针找“小”¶
右指针 j 从右往左找 第一个小于 pivot（5） 的数：
- j=7：arr[j]=6 >5 → 继续左移；
- j=6：arr[j]=1 <5 → 找到！交换 arr[i] 和 arr[j] → 数组变为 [1,3,8,4,2,7,5,6]，此时 i=1（基准已处理过第一个元素，左指针右移）。
步骤 3：移动左指针找“大”¶
左指针 i 从左往右找 第一个大于 pivot（5） 的数：
- i=1：arr[i]=3 ≤5 → 继续右移；
- i=2：arr[i]=8 >5 → 找到！交换 arr[i] 和 arr[j] → 数组变为 [1,3,5,4,2,7,8,6]，此时 j=5（右指针左移）。
步骤 4：重复直到指针相遇¶
继续循环：
- j=5：arr[j]=7 >5 → 左移；
- j=4：arr[j]=2 <5 → 交换 arr[i] 和 arr[j] → 数组变为 [1,3,2,4,5,7,8,6]，i=3；
- i=3：arr[i]=4 ≤5 → 右移；
- i=4：arr[i]=5 ≤5 → 右移；
- i=5：arr[i]=7 >5 → 交换 arr[i] 和 arr[j] → 数组变为 [1,3,2,4,5,7,8,6]，此时 i=j=5，循环结束。
最终结果¶
基准 5 归位到索引 5，数组分为左右两部分：
左子数组：[1,3,2,4]（全小于 5），右子数组：[7,8,6]（全大于 5）。
四、总结¶
快速排序的核心是 “选对基准+高效分区”：
- 基准选择：优先用“三数取中法”避免极端情况，保证分区平衡；
- 分区过程：通过左右指针移动，将数组分为“左小右大”，基准归位后递归排序子数组。
这种方法让快速排序在大多数情况下能以 O(n log n) 高效排序，是工程中最常用的排序算法之一。
小练习：试着用“三数取中法”对数组 [3,1,4,1,5,9,2,6] 选基准，并手动模拟分区过程吧！