快速排序的划分过程与优化策略 1. 题目描述 快速排序（Quick Sort）是一种基于 分治思想 的排序算法，其核心是 划分（Partition） 操作：从数组中选择一个基准元素（pivot），将数组划分为左右两部分，使得左边所有元素 ≤ pivot，右边所有元素 ≥ pivot，再递归排序左右两部分。划分过程的设计与优化直接影响快排的性能。 2. 基础划分过程（Lomuto 划分方案） Lomuto 划分是较易理解的实现，步骤如下： 选择基准 ：通常选最后一个元素作为 pivot（例如 arr[high] ）。 初始化指针 ：设置指针 i = low - 1 ，表示 ≤ pivot 的子数组的末尾。 扫描数组 ：用指针 j 从 low 到 high-1 遍历数组。 如果 arr[j] ≤ pivot ，则 i++ ，交换 arr[i] 和 arr[j] 。 放置基准 ：遍历结束后，将 pivot 放到正确位置：交换 arr[i+1] 和 arr[high] 。 返回基准索引 ：返回 i+1 作为划分点。 示例 （数组 [3, 7, 2, 8, 1, 5] ，pivot=5）： 步骤略（可逐步演示交换过程），最终划分结果： [3, 2, 1] 5 [7, 8] ，返回索引 3。 缺点 ：对已排序数组效率低，且重复元素多时可能导致不平衡划分。 3. 优化策略 1：Hoare 划分 Hoare 划分使用两个指针从两端向中间扫描，通常性能更好： 选择基准 ：选第一个元素 arr[low] 为 pivot。 初始化指针 ： i = low - 1 , j = high + 1 。 移动指针 ： 不断 i++ 直到 arr[i] ≥ pivot 。 不断 j-- 直到 arr[j] ≤ pivot 。 如果 i < j ，交换 arr[i] 和 arr[j] ，否则跳出循环。 返回划分点 ：最终返回 j 作为分界。 优点 ：交换次数更少，尤其适合重复元素多的数组。 4. 优化策略 2：随机化基准 在已排序或接近排序的数组中，固定选首尾元素作为 pivot 会导致最坏情况 O(n²)。 解决方法 ：随机选择 pivot 索引（例如在 [low, high] 中随机选），再与末尾元素交换，后续沿用 Lomuto 或 Hoare 划分。 效果 ：将最坏情况概率降至极低，期望时间复杂度为 O(n log n)。 5. 优化策略 3：三路划分（应对重复元素） 当数组中有大量重复元素时，标准划分会导致不平衡。三路划分将数组分为三部分： < pivot 的部分 = pivot 的部分 > pivot 的部分 步骤 （Dijkstra 三路划分）： 初始化指针： lt = low , gt = high , i = low ，选择 pivot = arr[low] 。 扫描： while i ≤ gt ： 若 arr[i] < pivot ，交换 arr[lt] 和 arr[i] ， lt++ , i++ 。 若 arr[i] > pivot ，交换 arr[gt] 和 arr[i] ， gt-- （ i 不变）。 若相等， i++ 。 递归排序 [low, lt-1] 和 [gt+1, high] ，中间等于 pivot 的部分已就位。 优点 ：重复元素多时效率高，避免对相等元素的重复比较。 6. 优化策略 4：小数组切换为插入排序 递归到小规模子数组时，快速排序的递归开销可能比排序本身更大。 常用策略 ：当子数组长度 ≤ 16（经验值）时，改用插入排序。 7. 总结与复杂度 平均时间复杂度 ：O(n log n)，最坏 O(n²)（通过随机化可避免）。 空间复杂度 ：O(log n) 递归栈空间。 稳定性 ：非稳定排序（划分时可能改变相同元素的相对顺序）。 实际应用 ：如 C++ 的 std::sort 、Java 的 Arrays.sort() 在基础类型排序中使用三路划分 + 插入排序优化。 通过这些优化，快速排序在实践中成为最通用的高效排序算法之一。