java快速排序时间限制

Question

这段代码有时工作正常，但在某些测试中

s Time Limit. What

是错误？

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

我尝试检查像 {3,2,1} 或 {3,7,4,2,1,9} 这样的短数组

s ok, but if it

是 40 或 100 个数字 -> TimeLimit。我创建分区算法，并采用随机主元。之后，我检查随机数是否等于 min，然后更改它。我计算迭代次数并对左侧和右侧进行快速排序。

Answer 1

当被分区的（子）数组仅重复相同的值时，例如 [2, 2, 2] 或 [5, 5]，以下循环将永远不会退出：

    while (A[x] == Z) {
        x = (int)(Math.random() * (r - l + 1) + l);
    }