我目前正在用Java编写快速排序算法来对随机的整数数组进行排序,然后使用System.nanoTime()对它们进行计时.这些数组的大小是10的幂,从10 ^ 3开始到10 ^ 7结束.此外,随机列表具有不同的属性.我正在整理纯粹的随机列表,列表中包含一些相同的值(很少),反向排序列表,排序列表和几乎排序的列表.
排序有效.它在数组上递归执行快速排序,直到它需要排序30个元素或更少的数组,在这种情况下,它执行插入排序.
一切都很好10 ^ 3和10 ^ 4但是一旦我达到10 ^ 5的值,它只会对随机,几个独特和随机列表进行排序,但在排序几乎排序和排序的列表时会产生堆栈溢出错误.
我不相信问题在于生成列表的方式,因为堆栈溢出发生在排序算法中(编译器引用的行是findPivot()方法中的第一行).此外,它通常会在崩溃之前对1到6个列表进行排序.因此,必须以某种方式使算法本身与几乎排序和排序的列表进行交互.此外,反向列表的生成涉及调用用于创建排序列表的代码(然后将其反转).
另外,我觉得不太可能,这个问题仅仅是不必,因为某些原因,通过递归在近分类和排序列表显著多次调用该分区关闭阵列的部分,而不是其他列表类型的算法,如它可以对10 ^ 7值的随机列表进行排序,这将需要比具有10 ^ 5值的近似排序列表更多的分区.
我意识到它必须与这些列表类型如何与我的快速排序的递归相互作用有关,但如果有人可以阐明它会很棒.我把代码放到了完整的快速排序算法和下面的随机列表生成器中.
快速排序算法
/**
* Performs a quick sort given the indexes of the bounds of an integer array
* @param arr The array to be sorted
* @param highE The index of the upper element
* @param lowE The index of the lower element
*/
public static void quickSort(int[] arr, int highE, int lowE)
{
//Only perform an action if arr.length …我已经编写了一个readInt()方法来读取System.in中的整数,但由于某种原因,返回的每个整数都是10.这不管数字是一位还是几位而且让我感到困惑.我的代码在下面,我哪里出错了？
/**
* @return The next integer read from the Input Stream
*/
public static int readInt() throws IOException {
BufferedInputStream in = new BufferedInputStream(System.in);
char c = (char) in.read();
int num = 0, cNum = Character.getNumericValue(c);
//Checks that the current value of c is in fact a single digit number (as it must be to be a char and an int)
while (cNum > -1 && cNum < 10) {
num = num * 10 + cNum;
c = …