Quicksort(Java)导致stack.verFlow在array.length> 60k
发布时间：2020-12-15 04:56:02 所属栏目：Java 来源：网络整理
导读：我的代码正常工作(据我所知)直到我的输入数组大小(a.length)大约为62,000,此时我一直得到StackOverFlowError.我以前曾使用2次递归调用quicksort(小于和大于pivot q),然后我切换到尾递归.如您所见,我选择了pivot作为数组末尾的值.我知道这不是选择枢轴的最佳
|
我的代码正常工作(据我所知)直到我的输入数组大小(a.length)大约为62,000,此时我一直得到StackOverFlowError.我以前曾使用2次递归调用quicksort(小于和大于pivot q),然后我切换到尾递归.如您所见,我选择了pivot作为数组末尾的值.我知道这不是选择枢轴的最佳方法,但我仍然不应该看到StackOverFlowErrors的数组大小这么小,对吧？可能是什么导致了这个？提前致谢！这是我的代码：
public static void quicksort(int[] a,int p,int r)
{
int q;
while (p < r)
{
q = partition(a,p,r);
quicksort(a,q - 1);
p = q + 1;
}
}
public static int partition(int[] a,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等人).通过随机化排序(选择随机枢轴),没有特定的输入引发其最坏情况的行为.
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,pivot);
quicksort(arr,pivot + 1,right);
}
}
private static int randomizedPartition(int[] arr,int right)
{
int swapIndex = left + rand.nextInt(right - left) + 1;
swap(arr,swapIndex);
return partition(arr,right);
}
private static int partition(int[] arr,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,j);
else
return j;
}
}
private static void swap(int[] arr,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,arr.length - 1);
System.out.print("After sort: ");
for (int i = 0; i < 20; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |