使用大尺寸(100000)数组执行快速排序时出现Java StackOverflower错误
在系统中处理衡量快速排序效率的作业。纳米时代。我的代码适用于其他数组大小(例如100;1000;10000),但是,当我尝试使用大小为100000的数组的方法时,我收到一个StackOverflower错误。还值得注意的是,对于InsertionSort和BubbleSort,我使用了大小为100000的数组
我们的目标是运行QuickSort 105次,测量前5次之后的100次,使用数组以纳米时间测量运行时间
首先,我创建一个预定大小的随机整数数组。接下来,我将克隆该int数组并将克隆传递给所需的排序方法(本例中为快速排序)。最后,我创建了一个方法,使用QuickSort运行所需的次数。方法如下:
public static void quickSort(int[] unsortedArray, int size, int max) {
long averageTime = 0;
for (int i = 0; i < RUN_TIMES; i++) {
if (i < 5) {
QuickSort.quickSort(unsortedArray);
} else {
long startTime = System.nanoTime();
QuickSort.quickSort(unsortedArray);
long stopTime = System.nanoTime();
long runTime = stopTime - startTime;
averageTime = averageTime + runTime;
}
}
System.out.println("Quicksort time for size " + size +
" and max " + max + ": " + averageTime / DIVISOR);
}
运行时间设置为105,除数设置为100。讲师提供的快速排序代码如下所示:
public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
}
private static void quickSort(int[] list, int first, int last) {
if (last > first) {
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
private static int partition(int[] list, int first, int last) {
int pivot = list[first]; // Choose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backward search
while (high > low) {
// Search forward from left
while (low <= high && list[low] <= pivot)
low++;
// Search backward from right
while (low <= high && list[high] > pivot)
high--;
// Swap two elements in the list
if (high > low) {
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high] >= pivot)
high--;
// Swap pivot with list[high]
if (pivot > list[high]) {
list[first] = list[high];
list[high] = pivot;
return high;
}
else {
return first;
}
我做错了什么?最后一个想法是,我正在更新的MacBookPro上使用NetBeans。只是想确定我分享了一切。任何帮助都将不胜感激
更新:这是我用来生成数组的代码:
private static int[] createArray(int size, int maxValue) {
int arraySize = size;
/*
Create array of variable size
Random int 1 - 999
*/
// Constructor for random and variable declaration
Random random = new Random();
int x;
// Constructor for ArrayList<Integer>
ArrayList<Integer> tempArrayList = new ArrayList<>();
// While loop used to create ArrayList w/100 unique values
while (tempArrayList.size() < arraySize) {
// Creates int value between 1 and 999
x = random.nextInt(maxValue) + 1;
// Checks if generated value already exists within ArrayList
if(!tempArrayList.contains(x)) {
// Add to ArrayList
//System.out.println("Added: " + x);
tempArrayList.add(x);
} else {
// Do nothing
} // end if - else
} // end while loop
// Convert ArrayList<Integer> to int[]
int[] arrayList = tempArrayList.stream().mapToInt(i -> i).toArray();
return arrayList;
} // end createArray method
# 1 楼答案
简短版本:您的列表已排序,QS需要对已排序的列表进行大量递归
快速排序是一种递归算法,最坏情况下的时间复杂度为
O(n)
,在对列表排序时,对于您的轴心选择(第一项),可以实现该算法在第一次迭代之后,它是这样的,因为快速排序已经就位,即它修改了输入数组
在第一次迭代之后,该数组上的快速排序需要
n
递归或100000
。太多了。考虑一个更好的排序算法,或者一个不使用递归的算法,或者考虑没有递归地重写它。# 2 楼答案
您已经编写了一个递归算法,它对堆栈施加了很大的压力,然后给它一个大数据集,给定堆栈压力与问题大小的平方成正比,这就不存在堆栈溢出的原因。将算法重新编码为循环,不要在堆栈上留下太多垃圾