对于家庭作业，我必须编写 QuickSort 算法的实现，并使用它以某种随机顺序对包含 10 万个数字的列表进行排序。
在作业的第一部分，我必须使用数组的第一项作为基准元素。这确实返回了一个排序列表。但是，对于作业的第二部分，我必须使用最后一项作为基准，这会导致 StackOverflowException。当我在 8 条记录的较小集合中尝试它时，它确实可以正常工作。我一直在查看我的代码，但我无法弄清楚我在哪里犯了错误。任何帮助将不胜感激。我的代码如下:
public class QuickSort {
private QuickSortStrategyEnum quickSortStrategy;
public QuickSort(QuickSortStrategyEnum quickSortStrategy) {
this.quickSortStrategy = quickSortStrategy;
}
public List<Integer> sortIntegerArray(List<Integer> arrayList, int left, int right) {
if ( left >= right ) {
return arrayList;
}
int i = partition(arrayList, left, right);
if (i <= right) {
int pivotNew = partition(arrayList, i, right);
int pivotIndex = arrayList.indexOf(pivotNew);
arrayList = sortIntegerArray(arrayList, left , pivotIndex - 1);
arrayList = sortIntegerArray(arrayList, pivotIndex + 1, right);
}
return arrayList;
}
private int partition(List<Integer> arrayList, int left, int right) {
int pivot = getPivot(arrayList, left, right);
int i = left + 1;
for (int j = i; j <= right; j++) {
if (arrayList.get(j) < pivot) {
Collections.swap(arrayList, j, i);
i++;
}
}
Collections.swap(arrayList, left, i - 1);
return i;
}
private int getPivot(List<Integer> arrayList, int left, int right) {
int pivot = 0;
switch (quickSortStrategy) {
case FIRST:
pivot = arrayList.get(left);
break;
case LAST:
pivot = arrayList.get(right);
break;
}
return pivot;
}
}
最佳答案
提示:如果 right == left + 1 会发生什么？
关于java - 快速排序算法抛出 StackOverflowException，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10164656/