我正在使用Java编写快速排序算法，以对随机整数数组进行排序并使用System.nanoTime()计时。这些数组的大小是10的幂次方，从10^3开始，到10^7结束。此外，这些随机列表具有不同的属性。我正在对纯随机列表、带有一些相同值的列表(fewUnique)、反向排序的列表、已排序的列表和几乎排序的列表进行排序。
排序运作正常。它在数组上递归地执行快速排序，直到需要排序30个元素或更少的数组，在这种情况下，它会执行插入排序。
对于10^3和10^4来说都很好，但一旦到达10^5，它只能对随机、少量唯一和随机列表进行排序，而在排序几乎排序和已排序的列表时会遇到堆栈溢出错误。
我不认为问题在于列表生成方式，因为堆栈溢出发生在排序算法中(编译器引用的行是findPivot()方法中的第一行)。此外，它通常会在崩溃之前对1到6个列表进行排序。因此，它必须以某种方式与几乎排序和已排序的列表交互。此外，生成反转列表涉及调用创建已排序列表的代码(然后反转它)。
此外，我认为问题不太可能仅仅是由于算法需要以某种原因在几乎排序和已排序列表中通过递归将数组的某些部分划分出来的次数要比其他列表类型显著地多，因为它可以对具有10^7值的随机列表进行排序，这将需要比具有10^5值的几乎排序列表更多的划分。
我意识到这必须与这些列表类型如何与我的快速排序递归交互有关，但如果有人能够解释一下就太好了。我已经将完整的快速排序算法代码和随机列表生成器代码放在下面。
排序运作正常。它在数组上递归地执行快速排序，直到需要排序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 > 30, otherwise insertion sort [recursive base case])
if (lowE + 29 < highE)
{
//Get the element and then value of the pivot
int pivotE = findPivot(arr, highE, lowE);
int pivotVal = arr[pivotE], storeE = lowE;
//Swap the pivot and the last value.
swapElements(arr, pivotE, highE);
//For each element in the selection that is not the pivot, check to see if it is lower than the pivot and if so, move it to the leftmost untouched element.
for (int i = lowE; i < highE; i++)
{
if (arr[i] < pivotVal)
{
swapElements(arr, storeE, i);
//Increment storeE so that the element that is being switched moves to the right location
storeE++;
}
}
//Finally swap the pivot into its proper position and recrusively call quickSort on the lesser and greater portions of the array
swapElements(arr, storeE, highE);
//Lesser
quickSort(arr, storeE - 1, lowE);
//Greater
quickSort(arr, highE, storeE + 1);
}
else
{
insertSort(arr, highE, lowE);
}
}
/**
* Finds the pivot element
* @param arr The array to be sorted
* @param highE The index of the top element
* @param lowE The index of the bottom element
* @return The index of the pivot.
*/
public static int findPivot(int[] arr, int highE, int lowE)
{
//Finds the middle element
int mid = (int) Math.floor(lowE + (highE - lowE) / 2);
//Returns the value of the median of the first, middle and last elements in the array.
if ((arr[lowE] >= arr[mid]) && (arr[lowE] >= arr[highE]))
{
if (arr[mid] > arr[highE]) {return mid;}
else {return highE;}
}
else if ((arr[mid] >= arr[lowE]) && (arr[mid] >= arr[highE]))
{
if (arr[lowE] > arr[highE]) {return lowE;}
else {return highE;}
}
else
{
if (arr[lowE] > arr[mid]) {return lowE;}
}
return mid;
}
/**
*Performs an insertion sort on part of an array
* @param arr The array to be sorted.
* @param highE The index of the top element.
* @param lowE The index of the low element.
*/
public static void insertSort(int[] arr, int highE, int lowE)
{
//Sorts elements lowE to i in array, with i being gradually incremented.
for (int i = lowE + 1; i <= highE; i++)
{
for (int j = i; j > lowE; j--)
{
if (arr[j] < arr[j - 1])
{
swapElements(arr, j, j-1);
}
else {break;}
}
}
}
随机列表生成器
/**
* Creates a random list
* @param arr The array to place the list inside of
*/
public static void randomList(int[] arr)
{
//Places a random number at each element of the array
for (int i = 0; i < arr.length; i++)
{
arr[i] = (int) Math.floor(Math.random() * RAND_MAX);
}
}
/**
* Creates a nearly sorted list of random numbers
* @param arr the array to place the list inside of
*/
public static void nearSortList(int[] arr)
{
//Creates a sorted list in arr
sortList(arr);
int swaps = (int) (Math.ceil(Math.pow((Math.log(arr.length)), 2.0)));
//The two values to be switched each time
int a, b;
//Performs a number of swaps equal to swaps [log(N) ^ 2] rounded up, with numbers switched no more than ln(N) places away
for (int i = 0; i < swaps; i++)
{
a = (int) Math.floor(Math.random() * arr.length);
b = (int) (a + Math.random() * 2 * Math.log(arr.length) - Math.log(arr.length));
//Accounts for cases in which b is either greater or smaller than the array bounds
if (b < 0)
{
b = -b;
}
else if (b >= arr.length)
{
b = -1 * (arr.length - b);
}
swapElements(arr, a, b);
}
}
/**
* Creates a random list with many unique values in
* @param arr the array to place the list inside of
*/
public static void fewUniqueList(int[] arr)
{
int[] smallArr = new int[(int) Math.floor(Math.pow(arr.length, 9.0 / 10.0))];
//Creates a smaller array of random values
randomList(smallArr);
//Fills the larger list up with values from the smaller list, ensuring aproximately N / N ^ (9/10) instances of each number in the array and ensuring, at most, there are N ^ (9/10) (rounded down) unique values in the large array
for (int i = 0; i < arr.length; i++)
{
arr[i] = smallArr[(int) Math.floor(Math.random() * smallArr.length)];
}
}
/**
* Creates a reversed list of random numbers
* @param arr the array to place the list inside of
*/
public static void reversedList(int[] arr)
{
//Creates a sorted list in arr
sortList(arr);
//Switches each ith elements with its mirror on the other end of the array until the value of i reaches the middle of the array
for (int i = 0; i < (int) (arr.length / 2.0); i++)
{
swapElements(arr, i, arr.length - 1 - i);
}
}
/**
* Creates a sorted list of random numbers using a merge sort
* @param arr the array to place the list inside of
*/
public static void sortList(int[] arr)
{
//Creates a random list in arr
randomList(arr);
Arrays.sort(arr);
}
编辑: [已废弃]
编辑2:
我已经用以下代码替换了基本递归调用，只调用了最小的两个分区，根据EJPs的建议，但仍然没有解决问题。
if (storeE - 1 - lowE < highE - storeE + 1)
{
//Lesser
quickSort(arr, storeE - 1, lowE);
//Greater
quickSort(arr, highE, storeE + 1);
}
else
{
//Greater
quickSort(arr, highE, storeE + 1);
//Lesser
quickSort(arr, storeE - 1, lowE);
}
编辑3：
好的，现在很明显递归深度比我原先估计的要大得多，对于几乎排序和已排序的列表。但现在我需要找出这种情况的原因，以及为什么随机列表只有1000万个值时深度为28，而几乎排序和已排序的列表深度超过了3000。