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

问题是这不是真正的quicksort如何工作.Quicksort是一种递归算法,只能从外部调用一次.我们的想法是,在每次迭代中,您将数组分成两半 - 左半部分包含小于枢轴的所有元素,右半部分包含大于/等于枢轴的所有元素.然后你快速分配两半,最后把枢轴放在中间.

如果您快速分配的一方长度少于3个元素,您可以只交换这两个元素或保留它们,并完成该部分数组.

但是看起来你的代码看起来并不是这样 - 你从你的客户端调用Quicksort 6次,并且在quicksort你最多只进行一次交换的函数中.所以这不是一个人可以通过告诉你移动交换或其他东西来查看你的代码并进行调试的情况.你需要重温你的逻辑.

查看Wikipedia图表,了解在一次迭代中应该发生的事情的可视化示例:

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