0

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

这是我的代码

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 异常，我尝试调试我的代码，但无法弄清楚它哪里出错了？

4

2 回答 2

1

您有一个递归函数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()的某个地方。检查 wikipedia 或 stackoverflow 并使用正确的实现来验证您的代码。

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

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

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

然后你需要看看你的参数quicksort。我不相信您需要起始位置或数组长度。它应该只需要数组本身。

于 2013-08-05T20:00:50.540 回答
0

如果数组中有四个元素，则第一遍是 3 次比较 + 第二遍中的 2 + 第三遍中的 1 或 6 深。每次比较时，您都必须将某些东西压入堆栈。这表明考虑到其他代码调用子例程，您的堆栈深度为 8 级，但是如今的堆栈通常使用堆栈指针完成，并且可能有数千个条目长。JVM 组织解释了整体结构。

于 2013-08-05T16:48:32.017 回答