1

我正在尝试实现快速排序算法，这是我的代码：

public class Sort {

int count = 0;

public void Partition(int A[], int l, int h) {

    if ((h-l) > 1) {

    count += (h-l) - 1;    

        int pivot = A[l];
        int i = l+1;
        int temp;
        int j;

        for (j = l + 1; j < h; j++) {

            if (A[j] < pivot) {  // SWAP
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i++;
            }
            // else : j++            
        }

        temp = A[i-1];   
        A[i-1] = A[l];
        A[l] = temp;

        Partition(A, l, i-1);               
        Partition(A, i, A.length);

    }
  }
}

该代码确实对输入数组进行了排序，但是当我计算比较次数时，它给出的数字远大于原始比较次数。我加了一个断点，一步步移到代码中，发现问题出在最后两行：Partition(A, l, i-1); 分区（A，i，A，长度）；

在第二次调用中发送的“i”是第一次调用函数 Partition 产生的 i，而不是第一个代码中的“i”。例如，代码第一次在以下输入上运行：3 8 4 6 10 2 5 7 1 输出为：1 2 3 4 6 10 9 5 7 8 和 i = 3。然后第一次调用 Partition 需要 i （其中 i 等于 3）并不断更改 i 的值，当它最终完成时，i 的值与 3 不同，并且另一个错误值被发送到第二次递归调用。

我的问题是，有没有办法让这两个调用采用相同的参数 i，而无需任何人更改？

4

2 回答 2

1

试试这个。不要尝试在Partition;中进行排序 从那里，只需返回索引i（当然，您必须将返回类型更改为 int）。然后编写一个不同的方法来实现你的快速排序。

public static void quicksort(int[] n, int left, int right){
if (left<right){
int pivotindex=Partition(n, left, right);
quicksort(n, left, pivotindex-1);
quicksort(n, pivotindex+1, right);}
}

我用以下方法对此进行了测试，并且效果很好。

public static void main(String[] args){
int[] n= new int[8];
n[0]=3;
n[6]=2;
n[1]=5;
n[3]=20;
quicksort(n, 0, n.length);
for (int i=0; i<n.length; i++){
    System.out.print(n[i]+",");
}
}
于 2013-07-22T20:52:16.007 回答
0

由于Java使用按值传递，因此第一次调用无法更改参数的值i，因为被调用的方法没有引用它。
您可能期望第二个电话Partition是下一个电话。但是，第一次调用又会再调用Partition两次，导致下一次执行的参数值与Partition您预期的不同。

另外，请以小写字母开头您的方法名称。

于 2013-07-22T19:31:38.290 回答