gpt4 book ai didi

java - 计算快速排序中的比较次数给出 stackoverflow

转载 作者:行者123 更新时间:2023-12-01 14:16:43 27 4
gpt4 key购买 nike

我正在尝试编写一个程序来计算快速排序程序中的比较次数。

这是我的代码

package algo_quicksort;

public class Algo_quicksort {

public static int partition(int[]A,int p,int r){
int x=A[p];
int i=p+1;
int temp;
for(int j=p+1;j<r;j++){
if(A[j]<x){//if A[j] is bigger than the pivot do nothing
temp=A[j];
A[j]=A[i];
A[i]=temp;
i++;
}
}
temp=A[p];
A[p]=A[i-1];
A[i-1]=temp;
return i-1;
}
public static long quickSort(int[]A,int startPos,int length){
if(length==1){
return 0;
}
else{
if(startPos<length){
int pivot= partition(A,0,length);
quickSort(A,startPos,pivot+1);
quickSort(A, pivot+2,length);
return length-startPos-1;
}
else{
return 0;
}
}
}


public static void main(String[] args) {
int a[]={3,2,4};
System.out.println("# of comparisons is: " +quickSort(a,0,a.length));

System.out.println("A[] after quicksort is: ");

for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}

}
}

它适用于任何大小为 3 或更少的数组,但如果它大于这个值,它会在递归调用时给我一个 stackoverflow 异常,我尝试调试我的代码,但无法弄清楚哪里出了问题?

最佳答案

您有一个递归函数,quickSort()

通常,当您使用递归方法获得 stackoverflow 条件时,这是因为您没有正确获得“结束”条件(或何时停止),或者您的输入参数不正确。

我通过调整输入参数对您的代码进行了实验,并得到了以下结果。

int a[]={3,2,4,5};    
System.out.println("# of comparisons is: " +quickSort(a,0,a.length -1));
//changed from a.length to a.length - 1

结果

比较次数为:2快速排序后的A[]为:2 3 4 5

<小时/>

但是我不相信这是解决方法,因为如果我将数组更改为“int a[]={5,3,2,4};”,那么 stackoverflow 错误会再次发生:(

这让我相信你的最终条件有问题......在 quickSort() 的某个地方。检查维基百科或 stackoverflow 并使用正确的实现验证您的代码。

<小时/>

因此,在为此编写一些测试后,您的快速排序实现似乎不正确。如果长度为 1,它将返回零。但是,如果我向它传递一个长度为 1、值为 5 的数组,则返回零,而我期望的是 5。

这意味着您的停止条件不正确。经过一番谷歌搜索后,我发现了以下内容:

  1. 第一个=最后一个;数组中只有一个元素表示已排序。
  2. 第一个 > 最后一个;数组中没有值表示已排序。

然后你需要看看你对快速排序的论点。我不认为您需要起始位置或数组长度。它应该只需要数组本身。

关于java - 计算快速排序中的比较次数给出 stackoverflow,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18064000/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com