快速排序的切分（Partition）是核心步骤，以Lomuto方案为例：取末元素为pivot，i维护≤pivot区域右边界（初值low−1），j从low遍历至high−1；每遇arr[j]≤pivot则swap(arr[++i],arr[j])，最后swap(arr[i+1],arr[high])使pivot归位；双路扫描（Hoare法）通过left/right双向查找并交换，可缓解重复元素导致的分区失衡。
快速排序的切分（Partition）是整个算法的核心，它决定了每一轮递归中基准值能否落在最终位置，并影响左右子数组的平衡性。切分逻辑本身不难，但变量设计、边界处理和基准选择稍有偏差，就容易导致死循环、越界或性能退化。下面从实现到优化，分三块讲清楚。
切分逻辑的关键变量与流程
以最常用的 Lomuto 分区方案 为例（选末元素为 pivot），核心变量只有三个：
-
pivot：基准值，通常取
arr[high]； -
i：指向“已确认 ≤ pivot 区域”的右边界，初始为
low - 1； -
j：扫描指针，从
low遍历到high - 1，逐个比较。
逻辑本质是维护两个隐式区间：[low, i] 存放 ≤ pivot 的数，[i+1, j-1] 是待处理区，[j, high-1] 是未扫描区。每次 arr[j] ≤ pivot，就把 arr[j] 换进左边区域（即 swap(arr[++i], arr[j])），最后把 pivot 换到 i+1 位置。
双路扫描法：解决重复元素与边界僵持问题
当数组含大量重复值（如 [5,5,5,5,1,9]），单路扫描可能让所有相等元素都挤在一边，造成分区严重失衡。此时改用双路扫描（Hoare 分区）更鲁棒：
- 设
left = low + 1，right = high； -
left向右找第一个 > pivot 的元素； -
right向左找第一个 ≤ pivot 的元素； - 两者相遇前，交换它们；相遇后，将 pivot 与
right位置交换。
注意：right 必须先走，否则可能跳过 pivot 本身；比较符号必须带等号（如 a[right] ），否则重复值无法归位。
分区变量优化：不止是“随机”，更要“抗退化”
单纯随机选 pivot 可缓解最坏情况，但工程中更推荐三数取中法（Median-of-Three）：
- 取首、中、尾三个位置的元素，比如
arr[low]、arr[mid]、arr[high]； - 选出三者中位数，把它换到
arr[high]（或arr[low]），再执行标准 partition； - 该策略对已排序、逆序、近似有序数组天然免疫，避免递归深度飙升至 O(n)。
补充建议：当子数组长度 ≤ 10 时，直接切换为插入排序——小数组上插入排序常比快排更快，且减少递归开销。
