Java快速排序代码部分测试用例超时，请求排查错误原因

我的Java快速排序代码在短数组（如{3,2,1}、{3,7,4,2,1,9}）测试中运行正常，但处理40或100个元素的测试用例时出现超时。代码实现了自定义分区算法，随机选取基准值并避开选中最小值的情况，随后对左右子数组递归排序，求代码中的错误原因。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        QuickSort(A, 0, N - 1);
        for (int j = 0; j < N; j++){
            System.out.print(A[j] + " ");
        }
    }

    public static int Partition(int[] A, int l, int r) {
        int x = (int)(Math.random() * (r - l + 1) + l);
        int Z = A[l];
        for (int i = l; i <= r; i++) {
            if (A[i] < Z) {
                Z = A[i];
            }
        }
        while (A[x] == Z) {
            x = (int)(Math.random() * (r - l + 1) + l);
        }
        int C = l - 1;
        for (int i = l; i <= r; i++) {
            int y = A[i];
            if (y >= A[x]) {
                continue;
            }
            if (y < A[x]) {
                int fake = A[C+1];
                A[C+1] = A[i];
                A[i] = fake;
                ++C;
            }
        }
        return C + 1;
    }
    public static int[] QuickSort(int[] A, int l, int r){
        if (r - l + 1 <= 1) {
            return A;
        }
        if (l < r) {
            int Index = Partition(A, l, r);
            QuickSort(A, l,  Index - 1);
            QuickSort(A, Index, r);
        }
        return A;
    }
}

错误原因分析 #

1. 递归边界引发无限递归 #

QuickSort方法中的递归调用为：

QuickSort(A, l,  Index - 1);
QuickSort(A, Index, r);

当Partition返回的Index等于l时，第二个递归调用的范围还是[l, r]，与原调用范围完全一致，会直接陷入无限递归，这是超时的核心原因。比如当分区后所有元素都大于等于基准值时，C会保持l-1，返回C+1 = l，此时第二次递归永远处理原区间，无法终止。

2. 最小值判断逻辑存在死循环风险 #

Partition中先遍历找到最小值Z，再循环随机选取基准直到选中的元素不是最小值。但如果数组中所有元素都是最小值（如{2,2,2,...}），while (A[x] == Z)会永远成立，程序直接死循环，无法继续执行。

3. 基准值未归位，分区逻辑不完整 #

标准快速排序会将基准值交换到分区后的正确位置（即C+1的位置），但你的代码中基准值A[x]始终留在原位置。这意味着分区后的数组并没有真正以基准值为分割点，递归处理时会重复处理基准值，大幅降低效率，甚至触发无限递归。

4. 冗余条件判断增加不必要开销 #

分区中的两个条件if (y >= A[x])和if (y < A[x])是互斥的，完全可以合并为一个判断，冗余代码虽不直接导致超时，但会增加额外计算开销。

修正后的代码示例 #

import java.util.Scanner;
import java.util.Random;

public class Main {
    private static final Random random = new Random();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        quickSort(A, 0, N - 1);
        for (int num : A) {
            System.out.print(num + " ");
        }
    }

    public static int partition(int[] A, int l, int r) {
        // 随机选取基准索引
        int pivotIdx = l + random.nextInt(r - l + 1);
        // 将基准值交换到右端，方便统一处理
        swap(A, pivotIdx, r);
        int pivot = A[r];
        int C = l - 1;

        // 遍历数组，将小于基准的元素移到左侧
        for (int i = l; i < r; i++) {
            if (A[i] < pivot) {
                C++;
                swap(A, C, i);
            }
        }
        // 将基准值放到正确的分割位置
        swap(A, C + 1, r);
        return C + 1;
    }

    public static void quickSort(int[] A, int l, int r) {
        if (l >= r) {
            return;
        }
        int pivotPos = partition(A, l, r);
        // 递归处理左右子数组，避开已归位的基准值
        quickSort(A, l, pivotPos - 1);
        quickSort(A, pivotPos + 1, r);
    }

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

内容的提问来源于stack exchange，提问作者Форс