双指针快速排序详解：经典分区策略解析

快速排序概述与分区策略

快速排序（QuickSort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”。它通过选择一个“枢轴”（pivot）元素，将数组（或子数组）划分为两个子数组：一个子数组中的所有元素都小于枢轴，另一个子数组中的所有元素都大于枢轴。然后，对这两个子数组递归地进行快速排序，直到整个数组有序。

快速排序的效率在很大程度上取决于其分区（Partition）策略。常见的分区方案包括Lomuto分区和Hoare分区。本文将详细讲解一种基于双指针的Hoare式分区策略实现。

核心分区函数 getPivotIndex 详解

getPivotIndex 函数是本快速排序实现的关键，它负责选择一个枢轴，并重新排列数组中的元素，使得枢轴最终位于其排序后的正确位置，同时将小于枢轴的元素放到其左侧，大于枢轴的元素放到其右侧。

1. 枢轴选择

在该实现中，枢轴（pivotVal）被简单地选为当前子数组的第一个元素，即 arg[startIndex]。虽然这种选择方式简单直接，但在某些特定输入（如已排序或逆序数组）下可能导致性能下降到最坏情况。

int pivotVal = arg[startIndex]; // 枢轴值为子数组的第一个元素

2. 双指针移动与元素交换

函数使用两个指针 i 和 j。i 从 startIndex 开始向右移动，j 从 endIndex（不包含，即实际子数组的最后一个元素之后一位）开始向左移动。

• i 指针负责寻找比枢轴大的元素。
• j 指针负责寻找比枢轴小的元素。

int i = startIndex;
int j = endIndex;

while (i < j) {
    // 右侧遍历：j 指针从右向左移动，寻找小于或等于枢轴的元素
    // 如果 arg[--j] >= pivotVal，说明该元素已经在枢轴的右侧（或等于枢轴），继续向左移动
    while (i < j && (arg[--j] >= pivotVal));
    // 如果 i < j，说明 j 找到了一个小于枢轴的元素，将其移动到 i 指针当前位置
    if (i < j)
        arg[i] = arg[j];

    // 左侧遍历：i 指针从左向右移动，寻找大于或等于枢轴的元素
    // 如果 arg[++i] <= pivotVal，说明该元素已经在枢轴的左侧（或等于枢轴），继续向右移动
    while (i < j && (arg[++i] <= pivotVal));
    // 如果 i < j，说明 i 找到了一个大于枢轴的元素，将其移动到 j 指针当前位置
    if (i < j)
        arg[j] = arg[i];
}

这个循环的目的是在 i 和 j 相遇之前，不断地将小于枢轴的元素移到左侧，大于枢轴的元素移到右侧。当 j 找到一个 arg[j] < pivotVal 的元素时，它会停下；当 i 找到一个 arg[i] > pivotVal 的元素时，它也会停下。然后，arg[j] 的值被赋给 arg[i]，arg[i] 的值被赋给 arg[j]。需要注意的是，这里并不是传统的 swap 操作，而是先将 arg[j] 移动到 arg[i] 的位置，然后将 arg[i]（此时是旧的 arg[j] 值）移动到 arg[j] 的位置。这种赋值方式巧妙地避免了临时变量，但在理解上可能稍显复杂。

3. 枢轴的最终定位

当 i 和 j 相遇时（i == j），循环结束。此时，j（或 i）所指向的位置就是枢轴最终的正确位置。我们将最初选定的枢轴值 pivotVal 放置到这个位置。

arg[j] = pivotVal;
return j; // 返回枢轴的最终索引

getPivotIndex 函数返回枢轴在排序后的数组中的最终索引，这个索引将用于后续的递归调用。

递归排序主函数 quickSort

quickSort 函数是快速排序的入口点和递归实现的主体。它利用 getPivotIndex 函数来划分数组，并递归地对子数组进行排序。

static void quickSort(int[] arg, int startIndex, int endIndex) {
    // 基本情况：如果子数组的长度小于2，则无需分区，直接返回
    if (endIndex - startIndex < 2)
        return;

    // 获取枢轴的最终索引
    int pivotIndex = getPivotIndex(arg, startIndex, endIndex);

    // 对枢轴左侧的子数组进行递归排序
    quickSort(arg, startIndex, pivotIndex);
    // 对枢轴右侧的子数组进行递归排序（注意：pivotIndex + 1，因为枢轴本身已在正确位置）
    quickSort(arg, pivotIndex + 1, endIndex);
}

• 基本情况（Base Case）：当 endIndex - startIndex < 2 时，表示当前子数组只包含一个元素或没有元素，已经是有序的，因此递归停止。
• 分区与递归：首先调用 getPivotIndex 找到枢轴的最终位置 pivotIndex。然后，quickSort 函数会递归地调用自身，分别对 [startIndex, pivotIndex) 区间（左侧子数组）和 (pivotIndex, endIndex) 区间（右侧子数组）进行排序。注意，枢轴本身（pivotIndex 处）不再参与后续的递归排序，因为它已经处于其最终的正确位置。

完整代码实现

public class QuickSort_Impl {

    public static void main(String[] args) {
        int[] unsortedArray = {12, 3, 45, 23, 6, -4, -6, 10, 1, 8};

        System.out.println("原始数组:");
        for (int i : unsortedArray)
            System.out.print(i + " ");
        System.out.println("\n");

        quickSort(unsortedArray, 0, unsortedArray.length);

        System.out.println("排序后数组:");
        for (int i : unsortedArray)
            System.out.print(i + " ");
        System.out.println();
    }

    /**
     * 快速排序主函数
     * @param arg 待排序数组
     * @param startIndex 子数组起始索引 (包含)
     * @param endIndex 子数组结束索引 (不包含)
     */
    static void quickSort(int[] arg, int startIndex, int endIndex) {
        // 基本情况：如果子数组长度小于2，则无需分区，直接返回
        if (endIndex - startIndex < 2)
            return;

        // 获取枢轴的最终索引
        int pivotIndex = getPivotIndex(arg, startIndex, endIndex);

        // 对枢轴左侧的子数组进行递归排序
        quickSort(arg, startIndex, pivotIndex);
        // 对枢轴右侧的子数组进行递归排序
        quickSort(arg, pivotIndex + 1, endIndex);
    }

    /**
     * 分区函数：通过双指针移动定位枢轴，并划分数组
     * @param arg 待分区数组
     * @param startIndex 子数组起始索引 (包含)
     * @param endIndex 子数组结束索引 (不包含)
     * @return 枢轴在排序后的数组中的最终索引
     */
    private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
        int pivotVal = arg[startIndex]; // 选择子数组的第一个元素作为枢轴
        int i = startIndex;
        int j = endIndex;

        // 当 i < j 时，进行双指针遍历和元素移动
        while (i < j) {
            // j 指针从右向左移动，寻找小于枢轴的元素
            // 如果 arg[--j] >= pivotVal，说明该元素已经在枢轴的右侧或等于枢轴，继续向左移动
            while (i < j && (arg[--j] >= pivotVal));
            // 如果 j 找到了一个小于枢轴的元素，将其移动到 i 指针当前位置
            if (i < j)
                arg[i] = arg[j];

            // i 指针从左向右移动，寻找大于枢轴的元素
            // 如果 arg[++i] <= pivotVal，说明该元素已经在枢轴的左侧或等于枢轴，继续向右移动
            while (i < j && (arg[++i] <= pivotVal));
            // 如果 i 找到了一个大于枢轴的元素，将其移动到 j 指针当前位置
            if (i < j)
                arg[j] = arg[i];

        } // End Outer while

        // 将枢轴值放置到 j 指针最终停留的位置（即枢轴的正确排序位置）
        arg[j] = pivotVal;
        // 返回枢轴的最终索引
        return j;
    }
}

性能考量与注意事项

1. 时间复杂度与空间复杂度

• 平均时间复杂度：快速排序的平均时间复杂度为 O(n log n)。在大多数情况下，这种分区策略表现良好。
• 最坏时间复杂度：O(n^2)。当枢轴选择不当，导致每次分区都产生一个空子数组和一个 n-1 大小的子数组时（例如，在已排序或逆序数组中总是选择第一个或最后一个元素作为枢轴），就会出现最坏情况。
• 空间复杂度：O(log n)（平均），O(n)（最坏）。这主要取决于递归调用栈的深度。

2. 枢轴选择的影响

本实现中枢轴选择为子数组的第一个元素。这种简单的选择方式可能导致在特定输入（如已排序或逆序数组）下性能退化。为了提高快速排序的鲁棒性，可以考虑以下枢轴选择策略：

• 随机选择枢轴：从子数组中随机选择一个元素作为枢轴，可以有效避免最坏情况。
• 三数取中法：选择子数组的第一个、中间和最后一个元素，取它们的中位数作为枢轴。这种方法能更好地应对部分有序的数组。

3. 与传统快速排序的比较

本教程中的实现是一种经典的Hoare分区方案的变体。它通过双指针交替移动和赋值来完成分区，而不是传统的直接交换。这种赋值方式在某些场景下可能减少实际的内存操作，但其核心逻辑和Hoare分区是相似的。用户提到它可能比“标准”快速排序慢，这可能是因为：

• 枢轴选择：固定选择第一个元素作为枢轴，导致在特定输入下性能不佳。
• 具体实现细节：与高度优化的库函数（如Arrays.sort()在Java 7+中使用的Dual-Pivot Quicksort）相比，这种基础实现可能不具备相同的优化水平。
• 微观性能：每次赋值操作的开销，以及内循环条件的判断，都可能影响其在特定硬件或JVM上的微观性能。

然而，从算法复杂度角度看，这种实现仍然是高效的快速排序。

总结

本文详细介绍了Java中一种基于双指针的快速排序实现。通过深入解析 getPivotIndex 分区函数的工作原理以及 quickSort 的递归逻辑，读者可以清晰地理解该算法的内部机制。尽管枢轴选择策略和具体的赋值方式可能影响其在特定场景下的性能，但它仍然是理解和掌握快速排序原理的一个优秀示例。在实际应用中，为了获得最佳性能，通常建议使用标准库中经过高度优化的排序函数，或采用更高级的枢轴选择策略。