java - Java中的Quicksort算法程序

Question

我正在尝试用 Java 实现 QuickSort 算法程序，但我得到的答案不正确。

public class QuickSort {

    public static void main(String[] args){
        int arr[]={12,34,22,64,34,33,23,64,33};
        int i=0;
        int j=arr.length;
        while(i<j){
            i=quickSort(arr,i,i+1,j-1);

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

    public static int quickSort(int arr[],int pivot,int i,int j){

        if(i>j) {           
            swap(arr,pivot,j);
            return i;
        }

        while(i<arr.length&&arr[i]<=arr[pivot]) {
            i++;
        }

        while(j>=1&&arr[j]>=arr[pivot]) {           
            j--;
        }   
        if(i<j)
            swap(arr,i,j);

        return quickSort(arr,pivot,i,j);

    }   
    public static void swap(int[] arr,int i,int j) {
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

}

上面的程序给我的输出是:12 23 22 33 34 33 64 34 64

谁能告诉我怎样才能得到我想要的结果？

Answer 1

问题是这并不是快速排序的真正工作方式。快速排序是一种递归算法，只能从自身外部调用一次。这个想法是，在每次迭代中，您将数组分成两半 - 左半部分包含小于主元的所有元素，右半部分包含大于/等于主元的所有元素。然后对两半进行快速排序，最后将枢轴放在中间。

如果您要快速排序的一侧的长度少于 3 个元素，您可以交换这两个元素或保留它们，这样数组的那部分就完成了。

但看起来您的代码根本没有这样做 - 您从客户端调用 Quicksort 6 次，并且在 quicksort 函数中您最多进行一次交换。因此，这不是某人能够通过告诉您移动交换或其他东西来查看您的代码并对其进行调试的情况。您需要重新审视您的逻辑。

查看维基百科图表，了解在单次迭代中应该发生什么的直观示例:

http://en.wikipedia.org/wiki/File:Partition_example.svg