Как взять случайное число в качестве стержня в быстрой сортировке?

Question

Итак, я протестировал этот код, и он работает, если pivot является последним элементом массива, но если я пытаюсь запустить его с pivot, являющимся случайным элементом, результирующий массив не содержит некоторые элементы исходного массива.

public static void quickSort(int[] S){
    int n = S.length;
    if(n<2)
        return;
    int random = (int)(Math.random() * n);

    int pivot = S[random];
    int m = 0, k = n;
    int[] temp = new int[n];

    for(int i = 0; i < n-1; i++){
        if(S[i] < pivot)
            temp[m++] = S[i];
        else if(S[i] > pivot)
            temp[--k] = S[i];
    } 
    int[] L = Arrays.copyOfRange(temp,0,m);
    int[] E = new int[k-m];
    Arrays.fill(E,pivot);
    int[] G = Arrays.copyOfRange(temp,k,n);
    quickSort(L);
    quickSort(G);
    System.arraycopy(L,0,S,0,m);
    System.arraycopy(E,0,S,m,k-m);
    System.arraycopy(G,0,S,k,n-k);
}

Этот код выводит 1 1 2 2 2 43

Answer 1

Неправильный предел петли: i < n - 1.Таким образом, вы игнорируете последний элемент и, если он не больше, чем ось, он попадает не в ту часть.

Чтобы исправить это, вы должны включить в цикл и последний элемент: i <= n - 1.