Java中的快速排序算法程序

Question

我试图用Java实现快速排序算法程序，但得到的答案不正确

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 64

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

Answer 1

请在这里找到用Java实现的快速排序算法的全面工作代码

http://tech.bragboy.com/2010/01/quick-sort-in-java.html

Answer 2

public static int partition(int[] a, int p, int r){

        int i=p,j=r,pivot=a[r];

        while(i<j){

            while(i<r && a[i] <= pivot){
                i++;
            }

            while(j>p && a[j]>pivot){ 
                j--;
            }

            if(i<j){
                swap(a, i, j);
            }           
        }   
        return j;
    }

    public static void quickSort(int[] a, int p, int r){
        if(p<r){
            int q=partition(a, p, r);

            if(p==q){
                quickSort(a, p+1, r);
            }else if(q==r){
                quickSort(a, p, r-1);
            }else {
                quickSort(a, p, q);
                quickSort(a, q+1, r);
            }

        }
    }

    public static void swap(int[] a, int p1, int p2){
        int temp=a[p1];
        a[p1]=a[p2];
        a[p2]=temp;
    }

Answer 3

您的循环工作不正常。请参阅解决Quick Sort问题的代码

static void quickSort (int[] numbers, int low, int high)
{
    int i=low;
    int j=high;
    int temp;
    int middle=numbers[(low+high)/2];

    while (i<j) {

        while (numbers[i]<middle) {
            i++;
        }

        while (numbers[j]>middle) {
            j--;
        }

        if (i<=j) {
            temp=numbers[i];
            numbers[i]=numbers[j];
            numbers[j]=temp;
            i++;
            j--;
        }
    }

    if (low<j) {
        quickSort(numbers, low, j);
    }

    if (i<high) {
        quickSort(numbers, i, high);
    }
}

参考Quick sort.

Answer 4

这是一个快速排序算法

package drawFramePackage;
    import java.awt.geom.AffineTransform;
    import java.util.ArrayList;
    import java.util.ListIterator;
    import java.util.Random;
    public class QuicksortAlgorithm {
        ArrayList<AffineTransform> affs;
        ListIterator<AffineTransform> li;
        Integer count, count2;
        /**
         * @param args
         */
        public static void main(String[] args) {
            new QuicksortAlgorithm();
        }
        public QuicksortAlgorithm(){
            count = new Integer(0);
            count2 = new Integer(1);
            affs = new ArrayList<AffineTransform>();
            for (int i = 0; i <= 128; i++){
                affs.add(new AffineTransform(1, 0, 0, 1, new Random().nextInt(1024), 0));
            }
            affs = arrangeNumbers(affs);
            printNumbers();
        }
        public ArrayList<AffineTransform> arrangeNumbers(ArrayList<AffineTransform> list){
            while (list.size() > 1 && count != list.size() - 1){
                if (list.get(count2).getTranslateX() > list.get(count).getTranslateX()){
                    list.add(count, list.get(count2));
                    list.remove(count2 + 1);
                }
                if (count2 == list.size() - 1){
                    count++;
                    count2 = count + 1;
                }
                else{
                count2++;
                }
            }
            return list;
        }
        public void printNumbers(){
            li = affs.listIterator();
            while (li.hasNext()){
                System.out.println(li.next());
            }
        }
    }

也可在nathan's computer knowledge处获得说明，并提供说明 [守则] [/code] ``

Answer 5

ApacheHarmony和ApacheMahout中可能有许多quicksort的开源实现。你可以读

Answer 6

问题是，这并不是快速排序的工作原理。快速排序是一种递归算法，只能从自身外部调用一次。其思想是，在每次迭代中，将数组分成两半-左半部分包含小于轴的所有元素，右半部分包含大于/等于轴的所有元素。然后你把两半快速分类，最后把枢轴放在中间。

如果要进行快速排序的那一方的长度小于3个元素，则只需交换这两个元素或将其保留，数组的这一部分就完成了

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

查看Wikipedia图表，了解一次迭代中应该发生什么的可视示例：

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