Java实现双指针快速排序：一种经典分区策略的深入解析

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

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];
}

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

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);
}

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;
    }
}