我正在审查算法的东西并停留在java中的一个简单的快速排序算法实现中
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
int arr[];
boolean randomPick;
Random rand = null;
public QuickSort(int[] inputArray) {
arr = inputArray;
randomPick = false;
}
public QuickSort(int[] inputArray, boolean random) {
arr = inputArray;
if (random) {
randomPick = true;
rand = new Random(System.currentTimeMillis());
}
else {
randomPick = false;
}
}
public int[] sort() {
int start = 0;
int end = arr.length - 1;
try {
_sort(start, end);
}
catch (StackOverflowError e) {
System.out.println("StackOverflow: " + Arrays.toString(arr));
}
return arr;
}
private void _sort(int start, int end) {
int i = start;
int j = end;
int pivotLoc;
if (!randomPick) {
pivotLoc = (j + i) / 2;
}
else {
pivotLoc = rand.nextInt(j - i) + i;
}
int pivot = arr[pivotLoc];
while (i < j) { // swapping numbers around the pivot
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i < j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}
}
if (i - start > 1) {
_sort(start, i);
}
if (end - i > 1) {
_sort(i, end);
}
}
}
该代码可以选择中间数字作为枢轴,也可以随机选择一个数字作为枢轴,并通过_sort
循环调用对数组进行排序。它在第一种情况下有效,但在第二种情况下失败。
情况是:当它到达像这个{3,5,5}这样的子数组时,i==start==0和j==end==2。最后交换 5 和 5,i 变为 2,j 变为 1(i++ 和 j--)。然后因为i - start>1
它会_sort
一遍又一遍地调用并最终引发stackoverflow错误。然而,错误应该发生在第一种情况(固定枢轴)中,到目前为止还没有发生......
我不知道我的代码有什么问题。我知道阅读其他人编写的代码并不令人愉快,但有什么帮助吗?