Zac*_*lin 6 java arrays sorting algorithm
我目前正在用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 > 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:
我已经使用以下代码替换了基本的递归调用,以便仅在EJP建议时调用两个分区中的最小分区,但仍然没有解决问题.
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:
好吧,现在显而易见的是,递归深度远远大于我对于近乎排序和排序的列表所给予的信任.但现在我需要弄清楚为什么会出现这种情况,以及为什么随机列表的深度仅为10 ^ 7的值,但几乎排序和排序的列表的深度超过3000
对于随机数组，您可以划分大量数据。
但对于（几乎）排序的数组，您通常会一次划分 1 个元素。
因此，对于排序数组，堆栈大小最终将与数组的大小相同，而对于随机数组，它更有可能是该大小的对数。
因此，即使随机数组比接近排序的数组大得多，较小的数组抛出异常而较大的数组则不会抛出异常也就不足为奇了。
修改你的代码
在修复方面，正如EJP 指出的那样，您应该首先进行较小的分区以限制堆栈增长。但这本身并不能解决问题，因为Java 不支持尾部调用优化（嗯，它对于实现来说是可选的，据我了解这个问题）。
这里一个相当简单的修复是将函数放入 while 循环中，本质上是对尾部调用优化进行硬编码。
为了更好地理解我的意思：
public static void quickSort(int[] arr, int highE, int lowE)
{
while (true)
{
if (lowE + 29 < highE)
{
...
quickSort(arr, storeE - 1, lowE);
// not doing this any more
//quickSort(arr, highE, storeE + 1);
// instead, simply set the parameters to their new values
// highE = highE;
lowE = storeE + 1;
}
else
{
insertSort(arr, highE, lowE);
return;
}
}
}
好了，现在你已经有了基本的想法，这看起来会更好（功能上与上面相同，只是更简洁）：
public static void quickSort(int[] arr, int highE, int lowE)
{
while (lowE + 29 < highE)
{
...
quickSort(arr, storeE - 1, lowE);
lowE = storeE + 1;
}
insertSort(arr, highE, lowE);
}
当然，这实际上并不会首先执行较小的操作，但我将把它留给您来解决（似乎您已经对如何执行此操作有了一个很好的想法）。
这是如何运作的
对于一些虚构的值...
您当前的代码执行此操作：（缩进指示该函数调用内部发生的情况 - 因此增加缩进意味着递归）
quickSort(arr, 100, 0)
quickSort(arr, 49, 0)
quickSort(arr, 24, 0)
insertion sort
quickSort(arr, 49, 26)
insertion sort
quickSort(arr, 100, 51)
quickSort(arr, 76, 0)
insertion sort
quickSort(arr, 100, 74)
insertion sort
修改后的代码执行以下操作：
public static void quickSort(int[] arr, int highE, int lowE)
{
while (true)
{
if (lowE + 29 < highE)
{
...
quickSort(arr, storeE - 1, lowE);
// not doing this any more
//quickSort(arr, highE, storeE + 1);
// instead, simply set the parameters to their new values
// highE = highE;
lowE = storeE + 1;
}
else
{
insertSort(arr, highE, lowE);
return;
}
}
}
增加堆栈大小
不确定您是否考虑过这一点，或者它是否适用于您的参数，但您始终可以考虑使用命令行参数简单地增加堆栈大小-Xss。