快速排序的划分过程与优化策略 快速排序是一种基于分治思想的高效排序算法，其核心在于划分操作。我将详细讲解划分过程的不同实现方法、关键细节以及常见的优化策略。 1. 划分的基本思想 划分的目标是：对于一个给定的数组（或子数组）以及一个选定的“基准”元素，重新排列数组，使得所有小于基准的元素都位于基准之前，所有大于基准的元素都位于基准之后。划分完成后，基准元素就处于其最终排序位置。 2. 经典划分方法：Lomuto划分方案 这是一种直观但可能在某些情况下效率稍低的划分方法。 步骤描述： 选择基准：通常选择子数组的最后一个元素作为基准（pivot）。 初始化指针：设置一个指针 i ，初始指向子数组的起始位置的前一个位置（即 low - 1 ）。这个指针表示“小于基准”区域的右边界。 遍历数组：使用另一个指针 j 从子数组的起始位置（ low ）遍历到倒数第二个元素（ high - 1 ）。 比较与交换：对于每个位置 j 的元素 arr[j] ： 如果 arr[j] <= pivot ，则将指针 i 向右移动一位（扩大“小于等于基准”的区域），然后交换 arr[i] 和 arr[j] 。这样， arr[i] 及其左边的元素都 <= pivot 。 如果 arr[j] > pivot ，则只移动 j ，不做交换。 放置基准：遍历完成后，所有 <= pivot 的元素都在 i 及其左边。此时，基准（ arr[high] ）还在最后。将基准放到其正确的位置，即 i + 1 的位置。交换 arr[i + 1] 和 arr[high] 。 返回基准位置：返回 i + 1 作为本次划分后基准的最终索引。 示例（对子数组 [2, 8, 7, 1, 3, 5, 6, 4] 进行划分，pivot=4）： 初始： i = -1 , j = 0 , 数组为 [2, 8, 7, 1, 3, 5, 6, 4] j=0 : 2<=4 -> i=0 , 交换 arr[0] 和 arr[0] (无变化) -> [2, 8, 7, 1, 3, 5, 6, 4] j=1 : 8>4 -> 无交换 -> [2, 8, 7, 1, 3, 5, 6, 4] j=2 : 7>4 -> 无交换 -> [2, 8, 7, 1, 3, 5, 6, 4] j=3 : 1<=4 -> i=1 , 交换 arr[1] (8) 和 arr[3] (1) -> [2, 1, 7, 8, 3, 5, 6, 4] j=4 : 3<=4 -> i=2 , 交换 arr[2] (7) 和 arr[4] (3) -> [2, 1, 3, 8, 7, 5, 6, 4] j=5 : 5>4 -> 无交换 -> [2, 1, 3, 8, 7, 5, 6, 4] j=6 : 6>4 -> 无交换 -> [2, 1, 3, 8, 7, 5, 6, 4] 遍历结束。交换 arr[i+1] ( arr[3] =8) 和 arr[high] ( arr[7] =4) -> [2, 1, 3, 4, 7, 5, 6, 8] 返回基准索引 3。 特点： 逻辑清晰，代码简单。但在处理大量重复元素或已排序数组时，交换次数可能较多，导致效率下降。 3. 更高效的划分方法：Hoare划分方案 这是快速排序发明者Tony Hoare提出的原始方法，通常比Lomuto方案更高效，交换次数更少。 步骤描述： 选择基准：通常选择子数组的第一个元素作为基准（pivot）。当然也可以选中点或随机点，然后与第一个元素交换。 初始化指针：设置两个指针， i 初始指向子数组起始位置的前一个（ low - 1 ）， j 初始指向子数组结束位置的后一个（ high + 1 ）。 相向扫描： 将指针 i 向右移动，直到找到一个 >= pivot 的元素。 将指针 j 向左移动，直到找到一个 <= pivot 的元素。 如果 i < j ，则交换 arr[i] 和 arr[j] 。 如果 i >= j ，则划分结束，返回 j 作为划分点。 循环执行第3步。 示例（对子数组 [4, 2, 8, 7, 1, 3, 5, 6] 进行划分，pivot=4）： 初始： i = -1 , j = 8 , 数组为 [4, 2, 8, 7, 1, 3, 5, 6] i 右移， arr[0]=4>=4 ，停在 i=0 。 j 左移， arr[7]=6>4 -> j=6 (5>4) -> j=5 (3<=4)，停在 j=5 。 0 < 5 ，交换 arr[0] (4) 和 arr[5] (3) -> [3, 2, 8, 7, 1, 4, 5, 6] i 右移， arr[1]=2<4 -> i=2 (8>=4)，停在 i=2 。 j 左移， arr[4]=1<=4 ，停在 j=4 。 2 < 4 ，交换 arr[2] (8) 和 arr[4] (1) -> [3, 2, 1, 7, 8, 4, 5, 6] i 右移， arr[3]=7>=4 ，停在 i=3 。 j 左移， arr[3]=7>=4 ? 不， j 从4开始左移， j=3 。 3 >= 3 ，划分结束。返回 j=3 。 此时数组为 [3, 2, 1, 7, 8, 4, 5, 6] 。注意，基准4并不在最终位置，但保证了索引 j (3) 左边的元素都 <= pivot ? 不，这里 arr[3]=7>4 。Hoare划分的保证是： [low, j] 的元素都 <= pivot ， [j+1, high] 的元素都 >= pivot 。我们需要递归排序 [low, j] 和 [j+1, high] 。 特点： 交换次数少，效率通常更高。但逻辑稍复杂，且基准元素不一定在最终位置。 4. 针对划分的优化策略 划分的效率直接影响快速排序的整体性能。 基准选择优化： 问题： 如果总是选择第一个或最后一个元素作为基准，对于已排序或接近排序的数组，划分会极度不平衡（例如，总是一边没有元素，另一边是n-1个元素），导致算法退化为O(n²)时间复杂度。 策略： 随机化： 随机选择基准元素。这能有效避免最坏情况在特定输入下总是发生，将最坏情况的概率均摊。 三数取中： 取子数组的首、中、尾三个元素，选择其中值作为基准。这能在一定程度上避免极端划分。 绝对中位数（IntroSelect）： 在算法可能退化为O(n²)时，切换到线性时间的选择算法（如BFPRT）来寻找中位数作为基准，保证最坏情况也是O(n log n)，但常数因子较大，实践中常用于混合算法如内省排序（Introsort）。 处理重复元素： 问题： 当数组中存在大量重复元素时，标准划分可能产生不平衡的划分。 策略：三路划分 思想： 将数组划分为三部分： [小于pivot] , [等于pivot] , [大于pivot] 。 方法： 使用三个指针： lt （小于区的右边界）、 i （当前检查的元素）、 gt （大于区的左边界）。 过程： 初始化 lt = low - 1 , gt = high + 1 , i = low 。选择基准pivot。 当 i < gt ： 如果 arr[i] < pivot ，交换 arr[++lt] 和 arr[i] ，然后 i++ 。 如果 arr[i] > pivot ，交换 arr[--gt] 和 arr[i] 。注意，此时 i 不增加，因为交换过来的新元素还未检查。 如果 arr[i] == pivot ， i++ 。 划分结束后，得到三个区域： [low, lt] （小于pivot）， [lt+1, gt-1] （等于pivot）， [gt, high] （大于pivot）。递归时只需要对小于区和大于区进行递归排序，等于区已经就位。 优势： 对于包含大量重复元素的数组，能显著减少递归深度和比较次数。 小数组优化： 问题： 当子数组规模很小时（例如长度小于10），递归调用快速排序的开销可能比排序本身的开销还大。 策略： 当子数组长度小于某个阈值时，切换到简单的非递归排序算法，如插入排序。因为插入排序在小规模数据上常数因子很小，且是原地稳定排序。 5. 总结 划分是快速排序的灵魂。理解Lomuto和Hoare这两种基本划分方案是基础。在实际应用中，通过随机化基准选择、三路划分处理重复元素、以及小数组切换插入排序等优化策略，可以极大地提升快速排序在真实数据上的性能和鲁棒性，使其成为实践中最快的通用排序算法之一。