快速排序的三种划分（Partition）方法

题目描述
在快速排序算法中，划分（Partition）是核心步骤，其目标是将一个数组根据某个基准元素（pivot）重新排列，使得所有小于pivot的元素都在其左侧，所有大于pivot的元素都在其右侧。不同的划分方法会影响算法的性能和代码实现。本题要求掌握并实现三种经典的划分方法：Lomuto划分法、Hoare划分法、以及三路划分法。

解题过程

1. 理解划分的目标
   给定一个数组 arr 和其左右边界 left 和 right，选择一个基准元素 pivot。划分操作完成后，数组应满足：

   • arr[left...p-1] 中的所有元素 <= pivot (对于Lomuto和Hoare) 或 < pivot (对于三路划分的严格左段)。
   • arr[p+1...right] 中的所有元素 >= pivot (对于Lomuto和Hoare) 或 > pivot (对于三路划分的严格右段)。
   • 基准元素 pivot 自身位于最终的正确位置 p (对于Lomuto和Hoare) 或位于中间段 (对于三路划分)。

2. 方法一：Lomuto划分法
   这是最直观、最容易理解的划分方法。

   • 步骤详解：

     1. 选择基准： 通常选择最右侧的元素 arr[right] 作为基准 pivot。
     2. 初始化指针： 设置一个指针 i，初始化为 left - 1。i 及其左边的所有元素都代表“已处理且小于等于pivot”的部分。
     3. 遍历数组： 使用另一个指针 j 从 left 遍历到 right - 1（因为 right 是pivot）。
     4. 比较与交换： 对于每个 arr[j]：
        • 如果 arr[j] <= pivot，说明这个元素应该属于“小于等于pivot”的区域。我们将这个区域扩大一位：先执行 i = i + 1，然后交换 arr[i] 和 arr[j]。
        • 如果 arr[j] > pivot，则不做任何操作，j 继续向后移动。
     5. 放置基准： 遍历完成后，i 指向的是“小于等于pivot”区域的最后一个元素。此时，i+1 就是pivot应该在的正确位置。我们将 arr[i+1] 和 arr[right]（即pivot）交换。
     6. 返回基准位置： 返回 i+1 作为本次划分后基准的最终位置。

   • 代码示例（Python）：

     def lomuto_partition(arr, left, right):
         pivot = arr[right]  # 选择最右元素为基准
         i = left - 1        # 小于等于区的右边界
     
         for j in range(left, right): # j 从 left 遍历到 right-1
             if arr[j] <= pivot:
                 i += 1
                 arr[i], arr[j] = arr[j], arr[i] # 将小元素交换到小于等于区
         # 将基准放置到正确位置
         arr[i + 1], arr[right] = arr[right], arr[i + 1]
         return i + 1  # 返回基准的最终位置
     

   • 特点： 代码简洁，但当所有元素都相等时，会产生最坏情况 O(n²)，因为每次划分都极度不平衡（一部分为n-1，另一部分为0）。

3. 方法二：Hoare划分法
   这是快速排序发明者Tony Hoare提出的原始方法，通常比Lomuto法更高效，交换次数更少。

   • 步骤详解：

     1. 选择基准： 通常选择最左侧的元素 arr[left] 作为基准 pivot。
     2. 初始化指针： 设置两个指针，i 初始化为 left - 1，j 初始化为 right + 1。
     3. 相向扫描：
        • 让 i 从左向右移动，直到找到一个 >= pivot 的元素。
        • 让 j 从右向左移动，直到找到一个 <= pivot 的元素。
        • 如果此时 i < j，则交换 arr[i] 和 arr[j]。因为 arr[i] 这个“大”的在左边不对，arr[j] 这个“小”的在右边也不对，交换它们就向正确迈进了一步。
     4. 终止条件： 重复步骤3，直到 i >= j。此时，j 就是划分的边界。
     5. 返回边界： 返回 j。注意，基准元素不一定在 j 的位置，但保证 arr[left...j] <= pivot 且 arr[j+1...right] >= pivot。

   • 代码示例（Python）：

     def hoare_partition(arr, left, right):
         pivot = arr[left]  # 选择最左元素为基准
         i = left - 1
         j = right + 1
     
         while True:
             # 注意：先移动指针，再比较
             i += 1
             while arr[i] < pivot: # 找第一个 >= pivot 的
                 i += 1
     
             j -= 1
             while arr[j] > pivot: # 找第一个 <= pivot 的
                 j -= 1
     
             if i >= j:
                 return j # 返回划分边界 j
     
             arr[i], arr[j] = arr[j], arr[i]
     

   • 特点： 效率更高，但理解稍复杂。注意在递归调用时，区间应划分为 [left, j] 和 [j+1, right]。

4. 方法三：三路划分法
   这是处理包含大量重复元素的数组时的最优方法，可以将复杂度优化到接近 O(n)。

   • 步骤详解：

     1. 选择基准： 同样选择一个基准 pivot（例如 arr[left]）。
     2. 初始化指针： 设置三个指针：
        • lt（less than）：lt 及其左边的所有元素都 严格小于 pivot。初始为 left - 1。
        • i（current）：当前正在检查的元素索引。初始为 left。
        • gt（greater than）：gt 及其右边的所有元素都 严格大于 pivot。初始为 right + 1。
     3. 遍历与分类： 当 i < gt 时，循环进行：
        • 如果 arr[i] < pivot：说明它属于“小”区。将 arr[i] 与 lt+1 位置的元素交换，然后 lt++ 和 i++。因为 lt+1 可能是等于区的第一个元素，交换后等于区的元素被挪到了后面，而小的元素被挪到了前面。
        • 如果 arr[i] == pivot：说明它就在正确的位置（中间段），直接 i++ 即可。
        • 如果 arr[i] > pivot：说明它属于“大”区。将 arr[i] 与 gt-1 位置的元素交换，然后 gt--。注意，此时 i 不要自增，因为从 gt-1 换过来的元素还没有检查过。
     4. 划分结果： 循环结束后，数组被划分为三段：
        • [left, lt]：严格小于 pivot 的元素。
        • [lt+1, gt-1]：等于 pivot 的元素。
        • [gt, right]：严格大于 pivot 的元素。
     5. 递归： 只需要对严格小于和严格大于的两段进行递归排序，中间等于pivot的段已经有序。

   • 代码示例（Python）：

     def three_way_partition(arr, left, right):
         if left >= right:
             return
         pivot = arr[left]
         lt = left - 1
         i = left
         gt = right + 1
     
         while i < gt:
             if arr[i] < pivot:
                 lt += 1
                 arr[lt], arr[i] = arr[i], arr[lt]
                 i += 1
             elif arr[i] == pivot:
                 i += 1
             else: # arr[i] > pivot
                 gt -= 1
                 arr[gt], arr[i] = arr[i], arr[gt]
         # 递归排序小于区和大于区
         # quick_sort_3way(arr, left, lt)
         # quick_sort_3way(arr, gt, right)
         return lt, gt # 返回两个边界
     

   • 特点： 有效处理重复元素，是工程实践中首选的快速排序优化方案之一。

总结

• Lomuto法：易于理解和实现，是教学中的首选，但效率略低。
• Hoare法：快速排序的原始方法，交换次数少，效率更高。
• 三路划分法：应对含有大量重复元素的数组时性能最佳，可以避免重复元素导致的劣化。在实际应用中（如Java的Arrays.sort()），三路划分是标准库的常见选择。