快速排序的优化：双轴快速排序（Dual-Pivot Quicksort）

题目描述
双轴快速排序是传统快速排序的一种高效变体。在传统快速排序中，我们选择一个主元（pivot）将数组划分为两部分。而双轴快速排序则选择两个主元（通常要求pivot1 ≤ pivot2），将数组划分为三个部分：小于pivot1的元素、介于pivot1和pivot2之间的元素、以及大于pivot2的元素。然后递归地对这三个部分进行排序。这种划分方式在某些情况下能减少比较和交换的次数，从而提升性能。Java的Arrays.sort()在排序基本数据类型数组时就使用了这种算法。我们的任务是理解并实现双轴快速排序算法。

解题过程

1. 算法思想与划分目标
   双轴快速排序的核心思想是使用两个主元（pivot）将待排序数组 arr 在区间 [left, right] 内划分为三个连续的子数组，从而将原问题分解为三个规模更小的子问题。划分后的理想状态如下：

   • arr[left ... l-1]：包含所有小于主元 pivot1 的元素。
   • arr[l ... k-1]：包含所有大于等于主元 pivot1 且小于等于主元 pivot2 的元素。
   • arr[k ... right]：包含所有大于主元 pivot2 的元素。
     其中，l 和 k 是划分过程中需要确定的边界索引。我们最终的目标是让数组呈现 [<p1), [p1<=x<=p2], (>p2)] 的结构。

2. 主元选择
   主元的选择对算法效率至关重要。一个简单有效的方法是取数组头尾的两个元素，但确保 pivot1 <= pivot2。

   if (arr[left] > arr[right]) {
       swap(arr, left, right); // 保证 arr[left] <= arr[right]
   }
   int pivot1 = arr[left];  // 较小的主元
   int pivot2 = arr[right]; // 较大的主元
   

3. 初始化指针
   我们需要三个指针来跟踪当前处理的位置和划分的边界：

   • i = left + 1：当前正在检查的元素的索引。
   • l = left + 1：指向“中间部分”的起始位置（也是小于pivot1部分的下一个位置）。所有在索引 l 之前的元素（除了最初的pivot1）都小于 pivot1。
   • k = right - 1：指向“中间部分”的结束位置（也是大于pivot2部分的前一个位置）。所有在索引 k 之后的元素（除了最初的pivot2）都大于 pivot2。

   初始时，数组状态为：[pivot1, ...待排序区域..., pivot2]。l 和 i 从 left+1 开始，k 从 right-1 开始。

4. 分区过程（核心循环）
   分区过程通过一个循环完成，只要当前指针 i 还没有超过 k，就继续处理。
   循环条件：while (i <= k)

   在循环中，我们根据当前元素 arr[i] 的值与两个主元的比较结果，将其交换到合适的区域：

   • 情况一：arr[i] < pivot1

     • 操作：将 arr[i] 与 arr[l] 交换。
     • 解释：arr[i] 属于“小于pivot1”的区域。这个区域紧挨着 pivot1 的右边，由指针 l 标识末尾。交换后，这个小于主元的元素被移到了“小于区”的末端。由于被交换到位置 l 的元素（原 arr[l]）可能是我们接下来要处理的（它来自中间区域），或者其值未知，所以我们需要增加 l 来扩大“小于区”，同时增加 i 来检查下一个元素。
     • 代码：swap(arr, i, l); l++; i++;

   • 情况二：arr[i] > pivot2

     • 操作：将 arr[i] 与 arr[k] 交换。
     • 解释：arr[i] 属于“大于pivot2”的区域。这个区域在数组的右端，由指针 k 标识起始位置。交换后，这个大于主元的元素被移到了“大于区”的起始位置。此时，从位置 k 交换过来的元素（原 arr[k]）是一个尚未处理过的元素，所以我们不能增加 i，需要在下一次循环中检查这个新交换过来的值。我们只将 k 减一，表示“大于区”向左扩大了一位。
     • 代码：swap(arr, i, k); k--; // 注意，i 不增加

   • 情况三：pivot1 <= arr[i] <= pivot2

     • 操作：不进行交换。
     • 解释：arr[i] 本身就位于它应该属于的“中间区域”。我们只需简单地让 i 加一，继续检查下一个元素即可。指针 l 和 k 保持不变，因为中间区域的边界没有变化。
     • 代码：i++

   • 情况四（隐含）：arr[i] 等于 pivot1 或 pivot2

     • 处理：这种情况被包含在情况三中。因为我们的条件是 pivot1 <= arr[i] <= pivot2，所以等于主元的元素也会留在中间区域，只需执行 i++。

5. 放置主元
   当循环结束时（i > k），所有元素都已经被扫描并移动到了大致正确的位置。但是，两个主元（pivot1 和 pivot2）仍然在数组的两端（left 和 right 位置）。我们需要将它们移动到最终的正确位置。

   • 放置 pivot1：将 pivot1（在 left 位置）与“小于区”的最后一个元素交换。这个最后一个元素的位置是 l - 1。
     • swap(arr, left, l - 1);
   • 放置 pivot2：将 pivot2（在 right 位置）与“大于区”的第一个元素交换。这个第一个元素的位置是 k + 1。
     • swap(arr, right, k + 1);

   经过这一步后，两个主元就位，数组被清晰地划分为三个部分：

   • [left, l-2]：小于 pivot1 的部分。（因为 pivot1 现在在 l-1 的位置）
   • [l-1, k+1]：介于 pivot1 和 pivot2 之间的部分。（包含了刚刚放置好的两个主元）
   • [k+2, right]：大于 pivot2 的部分。

6. 递归排序
   现在，我们对三个子数组进行递归排序：

   • 对“小于pivot1”的部分排序：dualPivotQuicksort(arr, left, l - 2);
   • 对“介于pivot1和pivot2之间”的部分排序：dualPivotQuicksort(arr, l, k);（注意边界，l 现在是中间段的开始，k 是中间段的结束，因为主元已就位）
   • 对“大于pivot2”的部分排序：dualPivotQuicksort(arr, k + 2, right);

7. 基准情形（递归终止条件）
   和普通快速排序一样，当子数组的长度小于等于1时（即 left >= right），就不需要再排序了。

总结
双轴快速排序通过一次扫描将数组划分为三个部分，相比于单轴快速排序的两次划分，在某些情况下可以减少比较和交换操作。其关键在于维护三个指针（l, i, k）并在循环中根据当前元素的值将其正确地归类到三个区域之一。最后，将两个主元放置到正确位置，并递归处理三个子区间。