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");
}
答
它看起来像你的分区算法是基于在Wikipedia的Lomuto分区方案。但是,在*中,伪代码表示for j := lo to hi - 1
,它基于Pascal语法。在Pascal语言中,这意味着j
的最后一个值是hi - 1
。在类似C语言的语言中,例如Java,我们通常会在索引将会拥有最后一个值而不是最后一个值之后,使上限值为。这意味着在您的代码中,j
永远不会具有值hi - 1
。修正for
循环以确保j
确实取值r-1
通过您的示例使事情顺利进行。
非常感谢,for循环迭代次数少于它应该的次数,并且它在某些场合运行时是纯粹的运气。 – Linxy