Рекурсивный QuickSort в java не работает

Question

Я пытаюсь реализовать quicksort в java, который имеет последний элемент массива в качестве точки опоры. Однако, как представляется, не будет работать, даже если на бумаге он должен ..

Это выход:

before sort: 5 2 3 1 4 

after sort: 3 2 4 5 1 

Ожидаемый результат будет 1,2,3,4,5, но это Безразлично Кажется, это происходит.

public static void main(String[] args) { 
    int A[] = {5,2,3,1,0}; 
    ArrayUtils.printArray("before sort", A); 
    quick_sort(A, 0, A.length-1); 
    ArrayUtils.printArray("after sort", A); 
} 

public static void quick_sort(int[] A, int p, int r) { 
    if (p < r) { 
     int q = partition(A, p, r); 
     quick_sort(A, p, q-1); 
     quick_sort(A, q+1, r); 
    } 
} 

Я отслеживал проблему вниз, чтобы быть в разделе с отладчиком, но я не могу найти, где это. Кажется, что цикл иногда вызывает неправильный i, но иногда он работает правильно. Я не уверен, поэтому я спрашиваю.

public static int partition(int A[], int p, int r) { 
    int x = A[r]; 
    int i = p-1; 
    for(int j = p; j < r-1; j++) { 
     if (A[j] <= x) { 
      i = i + 1; 
      int temp = A[j]; 
      A[j] = A[i]; 
      A[i] = temp; 
     } 
    } 
    int temp = A[r]; 
    A[r] = A[i + 1]; 
    A[i + 1] = temp; 
    return i + 1; 
} 

где PrintArray() является

public static void printArray(String name, int[] array) { 
    if (array.length >= 10) { 
     System.out.print(name + ": \n"); 
    } else { 
     System.out.print(name + ": "); 
    } 

    for(int i = 0; i < array.length; i++) { 
     if (i % 10 == 0 && i > 0) { 
      System.out.print("\n"); 
     } 
     System.out.print(array[i] + " "); 

    } 
    System.out.println("\n"); 
} 

Answer 1

Похоже, ваш алгоритм разбиения выглядит основан на схеме секционирования Lomuto в Wikipedia. Однако в Википедии псевдокод говорит for j := lo to hi - 1, который основан на синтаксисе Pascal. В Pascal-подобных языках это означает, что последнее значение j равно hi - 1. В C-подобных языках, таких как Java, мы обычно делаем верхнюю границу значения после последним значением, которое будет иметь индекс, вместо последнего значения. Это означает, что в вашем коде j никогда не будет иметь значение hi - 1. Фиксирование цикла for, чтобы убедиться, что j действительно принимает значение r-1 заставляет все работать, с вашим примером.