实施快速排序 [英] Implementing Quicksort
问题描述
我正在尝试实施快速排序,但没有得到正确的结果.这是我的代码:
i am trying to implement quicksort but i am not getting correct results. Here is my code:
public static void quickSort(Comparable[] a, int start, int stop) {
if (start < stop) {
int pivot = partition(a, start ,stop);
System.out.print("Pivot: "+a[pivot]+" Array: ");
printArray(a);
quickSort(a,start,pivot-1);
quickSort(a,pivot+1, stop);
}
}
public static int partition(Comparable[] a, int start, int stop) {
Comparable pivot = a[stop];
int i = start;
int j = stop-1;
while (i < j) {
while( (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
i++;
while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
j--;
if(i < j)
swap(a, i,j);
}
swap(a,i, stop);
return i;
}
对于输入:{51,17,82,10,97,6,23,45,6,73},我得到结果:6 6 10 17 23 45 51 73 97 82对于输入:{12,9,4,99,120,1,3,10},我得到一个索引越界错误.希望在我出错的地方提供一些帮助.
For input: {51,17,82,10,97,6,23,45,6,73}, i am getting result: 6 6 10 17 23 45 51 73 97 82 For input: {12,9,4,99,120,1,3,10}, i am getting an index out of bounds error. Would appreciate some help in where i am going wrong.
推荐答案
你的两个问题无关.
{51,17,82,10,97,6,23,45,6,73}
的问题是 —stop == start + 1
会发生什么?然后i == start == stop - 1 == j
,所以你永远不会进入while
-loop,所以你无条件地swap(a, i, stop)
—即使a[i]
已经小于a[stop]
.
The problem with {51,17,82,10,97,6,23,45,6,73}
is — what happens when stop == start + 1
? Then i == start == stop - 1 == j
, so you never enter the while
-loop, so you unconditionally swap(a, i, stop)
— even if a[i]
was already less than a[stop]
.
{12,9,4,99,120,1,3,10}
的问题似乎是您没有阅读堆栈跟踪.;-) 假设你有一个不错的 Java 编译器和 JVM,它应该给你确切的行号和有问题的索引,所以你会看到问题出在这一行:
The problem with {12,9,4,99,120,1,3,10}
is seemingly that you didn't read the stacktrace. ;-) Assuming you have a decent Java compiler and JVM, it should have given you the exact line-number and problematic index, so you would have seen that the problem is in this line:
while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
一旦 j
到达 -1
.(如果 pivot
是感兴趣范围内的最小值,就会发生这种情况.)您只需要为此添加一个检查:
once j
gets to -1
. (This will happen if pivot
is the very least value in the range of interest.) You just need to add a check for that:
while(j > start && (isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
(并且,就此而言,对于 i
的相应情况:
(and, for that matter, for the corresponding case of i
:
while(i < stop && (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
)
...你需要学习如何调试你的代码.:-)
. . . and you need to learn how to debug your code. :-)
这篇关于实施快速排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!