快速排序实现未返回预期结果

Question

我一直在尝试在Java中编写快速排序算法，但它不能正常工作。我已经将代码与其他几个在线实现进行了比较，老实说，我无法找出问题所在。

public class Quicksort {
public void sort(int[] list){
sort(list, 0, list.length - 1);
}
private void sort(int[] list, int li, int hi){
if (li < hi){
int pi = partition(list, li, hi);
sort(list, li, pi - 1);
sort(list, pi + 1, hi);
}
}
private int partition(int[] list, int li, int hi){
int pivot = list[hi];
int i = (li - 1);

for (int j = li; j <= hi; j++){
if (list[j] < pivot){
i++;
swap(list, i, j);
}
}
swap(list, list[i + 1], list[hi]);
return (i + 1);
}
private void swap(int[] list, int a, int b){
if (a >= list.length || b >= list.length){
return;
}
int temp = list[a];
list[a] = list[b];
list[b] = temp;
}
private int getPivot(int[] list, int li, int hi){
int mi = hi / 2;
int chosen = Math.max(Math.max(list[hi], list[li]), list[mi]);
System.out.println(chosen);
return chosen;
}
}

Answer 1

在partition()的末尾交换枢轴时，将错误的参数传递给方法swap()

改变

swap(list, list[i + 1], list[hi]);

swap(list, i + 1, hi);

另外，以下检查方法swap():

if (a >= list.length || b >= list.length){
return;
}

不应该需要。由于上述错误，a和b的值可能过高，但如果代码正确，则不会发生这种情况。