快速排序的三种划分（Partition）方法 题目描述 划分（Partition）是快速排序算法的核心步骤，其目标是将数组根据某个基准元素（pivot）重新排列，使得 pivot 左侧的元素均不大于 pivot，右侧的元素均不小于 pivot。不同的划分方法会影响快速排序的性能和稳定性。常见的划分方法包括 Lomuto 划分、Hoare 划分和双指针挖坑法。本题要求详细理解这三种方法的实现细节、优缺点及适用场景。 解题过程 1. Lomuto 划分法 基本思想 ： 选择最右元素作为 pivot，维护一个指针 i ，使其指向已处理部分中最后一个小于等于 pivot 的元素。遍历数组时，若当前元素小于等于 pivot，则将其与 i+1 位置的元素交换，并移动 i 。最终将 pivot 交换到正确位置。 步骤 ： 设置 pivot = arr[high] ，初始化 i = low - 1 。 遍历 j 从 low 到 high-1 ： 若 arr[j] <= pivot ，则 i++ ，交换 arr[i] 和 arr[j] 。 交换 arr[i+1] 和 arr[high] （将 pivot 归位）。 返回 i+1 作为 pivot 的最终位置。 特点 ： 代码简洁，易于理解。 交换次数较多，效率低于 Hoare 法。 不保持原始相对顺序（不稳定）。 2. Hoare 划分法 基本思想 ： 使用两个指针从数组两端向中间扫描，左指针寻找大于 pivot 的元素，右指针寻找小于 pivot 的元素，交换二者，直到指针相遇。 步骤 ： 选择 pivot = arr[low] （也可选中间元素）。 初始化 i = low - 1 ， j = high + 1 。 循环执行： 左移 j 直到 arr[j] <= pivot 。 右移 i 直到 arr[i] >= pivot 。 若 i < j ，交换 arr[i] 和 arr[j] ；否则返回 j 作为划分点。 特点 ： 交换次数少，效率更高。 划分后 pivot 不一定在最终位置（需递归处理 [low, j] 和 [j+1, high] ）。 不稳定，但实际性能优于 Lomuto 法。 3. 双指针挖坑法 基本思想 ： 改进的 Hoare 法，将 pivot 视为“坑”，交替从右向左填坑，减少交换操作。 步骤 ： 选择 pivot = arr[low] ，保存其值，此时 low 位置为“坑”。 初始化 i = low ， j = high 。 循环执行： 从右向左移动 j ，找到第一个小于 pivot 的元素，将其填入坑中（ arr[i] = arr[j] ），此时 j 成为新坑。 从左向右移动 i ，找到第一个大于 pivot 的元素，将其填入坑中（ arr[j] = arr[i] ），此时 i 成为新坑。 重复直到 i == j ，将 pivot 填入最后坑中。 返回坑的位置 i 。 特点 ： 减少元素交换次数，仅赋值操作。 适用于对交换成本敏感的场景（如元素为大对象）。 不稳定，但代码实现较直观。 对比与选择建议 效率 ：Hoare 法通常最优，双指针法次之，Lomuto 法最差。 稳定性 ：三者均不稳定，可通过额外空间实现稳定划分（非原地排序）。 适用场景 ： Lomuto：教学或简单实现。 Hoare：实际工程中的首选。 双指针法：需最小化交换次数的场景。 总结 掌握三种划分方法的核心区别与实现细节，有助于根据具体问题优化快速排序的性能。实际面试中，需清晰阐述步骤并分析时间复杂度（平均 O(n)）与空间复杂度（O(1) 原地划分）。