实施快速排序

本文介绍了实施快速排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试实施快速排序，但没有得到正确的结果.这是我的代码:

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. :-)