Java中的递归QuickSort不工作

我想在java中实现一个快速排序，该快速排序以数组的最后一个元素作为关键点。然而，这似乎并没有工作，即使在纸张上它应该..Java中的递归QuickSort不工作

这是输出：

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

我已经跟踪调试器的分区问题，但我似乎无法找到它在哪里。它似乎为循环有时会产生一个错误的我，但有时它能正常工作..我不知道，这就是为什么我问。

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

来源

2016-11-24 Linxy

它看起来像你的分区算法是基于在Wikipedia的Lomuto分区方案。但是，在维基百科中，伪代码表示for j := lo to hi - 1，它基于Pascal语法。在Pascal语言中，这意味着j的最后一个值是hi - 1。在类似C语言的语言中，例如Java，我们通常会在索引将会拥有最后一个值而不是最后一个值之后，使上限值为。这意味着在您的代码中，j永远不会具有值hi - 1。修正for循环以确保j确实取值r-1通过您的示例使事情顺利进行。

来源

2016-11-24 19:45:48 ajb

非常感谢，for循环迭代次数少于它应该的次数，并且它在某些场合运行时是纯粹的运气。 – Linxy

Java中的递归QuickSort不工作

回答

相关问题