问题描述
我的代码正常工作(据我所知),直到我的输入数组大小( a.length
)大约为62,000,此时我一直得到的StackOverflowError
。我以前曾使用2次递归调用 quicksort
(小于和大于数据透视 q
)然后我切换尾递归。如您所见,我选择了pivot作为数组末尾的值。我知道这不是选择数据透视表的最佳方法,但我仍然不应该看到 StackOverFlowError
s,数组大小这么小,对吧?可能是什么导致了这个?提前致谢!这是我的代码:
My code works properly (to my knowledge) up until my input array size (a.length
) is around 62,000 at which time I consistently get a StackOverFlowError
. I previously had used 2 recursive calls to quicksort
(less than, and greater than the pivot q
) and then I switched to tail recursion. As you can see, I'm selecting the pivot to be the value at the end of the array. I know this isn't the best way to choose a pivot, but I still shouldn't be seeing StackOverFlowError
s with an array size this small, right? What could be causing this? Thanks in advance! Here's my code:
public static void quicksort(int[] a, int p, int r)
{
int q;
while (p < r)
{
q = partition(a, p, r);
quicksort(a, p, q - 1);
p = q + 1;
}
}
public static int partition(int[] a, int p, int r)
{
int j = p - 1;
int x = a[r];
for (int i = p; i < r; i++)
{
if (a[i] <= x)
{
j++;
swap(a, i, j);
}
}
j++;
swap(a, j, r);
return j;
}
private static void swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
推荐答案
最坏情况输入(排序顺序)使快速排序Θ(n ^ 2)。 分区总是在分区的一侧放置一个元素(Cormen等人)。通过随机化排序(选择随机数据)没有特定的输入引发其最坏情况行为。
The worst-case input (sorted order) makes quicksort Θ(n^2). Partition always puts a single element on one side of the partition (Cormen et al.). By randomizing the sort (choosing a random pivot) no particular input elicits its worst-case behavior.
import java.util.Random;
public class Quicksort
{
private static Random rand = new Random();
public static void quicksort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = randomizedPartition(arr, left, right);
quicksort(arr, left, pivot);
quicksort(arr, pivot + 1, right);
}
}
private static int randomizedPartition(int[] arr, int left, int right)
{
int swapIndex = left + rand.nextInt(right - left) + 1;
swap(arr, left, swapIndex);
return partition(arr, left, right);
}
private static int partition(int[] arr, int left, int right)
{
int pivot = arr[left];
int i = left - 1;
int j = right + 1;
while (true)
{
do
j--;
while (arr[j] > pivot);
do
i++;
while (arr[i] < pivot);
if (i < j)
swap(arr, i, j);
else
return j;
}
}
private static void swap(int[] arr, int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// Sort 100k elements that are in reversed sorted order
public static void main(String[] args)
{
int arr[] = new int[100000];
for (int i = 0; i < arr.length; i++)
arr[i] = arr.length - i;
System.out.println("First 20 elements");
System.out.print("Before sort: ");
for (int i = 0; i < 20; i++)
System.out.print(arr[i] + " ");
System.out.println();
quicksort(arr, 0, arr.length - 1);
System.out.print("After sort: ");
for (int i = 0; i < 20; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
这篇关于Quicksort(Java)导致在array.length>处的StackOverFlow; 60K的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!