Java右侧分区算法实现出错，求问题排查与修复方案

我正在开发一个以右侧元素为基准的Partition算法程序，运行结果不符合预期。输入数组[64, 17, 7, 3, 33]时，预期输出为[17, 7, 3, 33, 64]（基准元素33位于正确位置，左侧元素均小于它，右侧元素大于它），但实际得到[33, 17, 7, 3, 64]。以下是我的Java代码：

import java.util.Arrays;

public class PartitionPivotOnRight {

    public static int partition(int[] a) {
        int left = 0;
        int right = a.length - 2;
        int pivot = a.length - 1;

        while (left <= right) {
            while (left < a.length && a[left] < a[pivot])
                ++left;
            while (a[right] > a[pivot])
                --right;
            if (left <= right)
                swap(a, left++, right--);
        }
        swap(a, left, pivot);
        return left;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int N = 10;
        int[] a = new int[N];

        for (int i = 0; i < N; i++)
            a[i] = (int) (Math.random() * 100);

        System.out.println(Arrays.toString(a));
        System.out.println(partition(a));
        System.out.println(Arrays.toString(a));
    }
}

问题分析 #

代码存在两个核心问题：

1. 右侧指针越界风险：第二个while循环未判断right >= 0，当数组中所有元素都小于等于基准值时，right会持续递减至-1，触发ArrayIndexOutOfBoundsException。
2. 分区逻辑边界处理不严谨：第一个while循环的left < a.length范围过大（无需遍历到基准元素位置），且两个指针的循环条件未确保left不超过right，可能导致无效的指针移动，最终让基准元素被交换到错误位置。

另外需要明确：Partition算法仅保证基准元素左侧的元素均小于等于它、右侧元素均大于它，不保证左侧元素内部的排序，因此[3, 17, 7, 33, 64]也是正确的分区结果，与你预期的[17, 7, 3, 33, 64]仅左侧元素顺序不同，均符合分区要求。

修复后的代码 #

import java.util.Arrays;

public class PartitionPivotOnRight {

    public static int partition(int[] a) {
        int left = 0;
        int right = a.length - 2;
        int pivotIdx = a.length - 1;
        int pivotVal = a[pivotIdx]; // 提前缓存基准值，减少数组访问次数

        while (left <= right) {
            // 从左找第一个大于等于基准值的元素
            while (left <= right && a[left] < pivotVal) {
                left++;
            }
            // 从右找第一个小于等于基准值的元素，同时确保right不小于left
            while (right >= left && a[right] > pivotVal) {
                right--;
            }
            if (left <= right) {
                swap(a, left++, right--);
            }
        }
        // 将基准元素交换到正确的分区位置
        swap(a, left, pivotIdx);
        return left;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        // 测试目标数组
        int[] a = {64, 17, 7, 3, 33};
        System.out.println("输入数组：" + Arrays.toString(a));
        int pivotPos = partition(a);
        System.out.println("基准元素位置：" + pivotPos);
        System.out.println("分区结果：" + Arrays.toString(a));
    }
}

修复后的代码运行输入数组[64, 17, 7, 3, 33]会得到[3, 17, 7, 33, 64]，基准元素33位于索引3，左侧元素均小于它，右侧元素64大于它，符合分区要求。如果需要左侧元素有序，需在分区后额外执行排序逻辑，但这不属于Partition算法的职责。

内容的提问来源于stack exchange，提问作者Ezequiel Soler