在System.nanoTime中处理一个测量快速排序效率的赋值。我有适用于其他数组大小(例如100；1000；10000(的代码，但是，当我尝试使用100000大小的数组时，我收到了StackOverflowError。同样值得注意的是，我为InsertionSort和BubbleSort的100000大小的数组工作。
目标是运行QuickSort 105次，在前5次之后测量100次，使用阵列，以纳米时间测量运行时间。
首先，我创建一个预定大小的随机int数组。接下来，我将克隆int数组，并将克隆传递给所需的排序方法(本例中为QuickSort(。最后，我创建了一个方法来使用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);
}
RUN_ TIMES被设置为105并且DIVISOR被设置为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;
}
我做错了什么？最后一个想法是，我正在更新的MacBook Pro上使用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
简短版本：您的列表已排序，QS需要对排序列表进行大量递归。
QuickSort是一种递归算法，最坏情况下的时间复杂度为O(n)，当列表排序时，您可以选择枢轴(第一项(。
在第一次迭代之后，它就是这样，因为QuickSort在适当的位置进行排序，即它修改输入数组。
在第一次迭代之后，该阵列上的快速排序需要n递归或100000。太多了。考虑一个更好的排序算法，或者一个不使用递归的算法，或者考虑在没有递归的情况下重写它。
您已经编写了一个递归算法，它给堆栈带来了巨大的压力，然后给它一个大的数据集，假设堆栈压力与问题大小的平方成比例，那么为什么会出现堆栈溢出就不足为奇了。把你的算法重新编码为一个循环，不要在堆栈上留下太多垃圾。