QuickSort 给出不正确的排序顺序

Question

我是 Java 的新手，我正在尝试实施 QuickSort。下面是我的脚本。

public class QuickSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] ={5,6,7,4,1,3};
        QuickSort qs = new QuickSort();
        qs.quickSort(a,0,a.length-1);
        for(int i=0;i<a.length;i++) {
            System.out.println(a[i]);
        }

    }
    public void quickSort(int[] a,int left, int length) {

        if(left >= length) return;
        int index = partition(a,left,length);
        if(left < index) {
            quickSort(a,left,index-1);
        }
        else {
            quickSort(a,index,length);
        }
    }

    private  int partition(int[] a,int l, int length) {
        // TODO Auto-generated method stub
        int left = l;
        int right = length;
        int pivot = a[(left+right)/2];
        while(left <= right) {
            while(left < length && a[left] < pivot) {
                left++;
            } 
            while(right >= 0 && a[right] > pivot) {
                right--;
            }
            if(left <= right) {
                int temp = a[left];
                a[left]=a[right];
                a[right]=temp;
                left++;
                right--;
            }
        }
        return left;
    }

}

当我打印解决方案时，我得到以下顺序-

[1,3,6,4,5,7]

我无法找出错误，谁能帮我解决这个问题。

Answer 1

Quicksort 将数组分成两个较小的数组，分别位于主元的两侧。这意味着对快速排序的每次调用都应该导致对快速排序的两次调用。您的代码当前以递归方式调用快速排序，但只调用了一半。

Quicksort(array)
    pick a pivot
    Arrays left, right
    For each value in array
        If value < pivot
            Append to left array
        Else
            Append to right array
    Quicksort(left)
    Quicksort(right)
    Return join(left, right)

Answer 2

只需更改此

if(left < index) {
    quickSort(a,left,index-1);
}
else {
    quickSort(a,index,length);
}

至此

quickSort(a,left,index-1);
quickSort(a,index+1,length);

因为您需要对数组的每个分区递归排序！

Answer 3

试试下面的代码：

import java.util.ArrayList;

public class MyQuickSort {

/**
 * @param args
 */
public static void main(String[] args) {

    //int[] a = { 1, 23, 45, 2, 8, 134, 9, 4, 2000 };
    int a[]={23,44,1,2009,2,88,123,7,999,1040,88};
    quickSort(a, 0, a.length - 1);
    System.out.println(a);
    ArrayList al = new ArrayList();
}

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

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

    int x = a[p];
    int i = p-1 ;
    int j = r+1 ;

    while (true) {
        i++;
        while ( i< r && a[i] < x)
            i++;
        j--;
        while (j>p && a[j] > x)
            j--;

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

private static void swap(int[] a, int i, int j) {
    // TODO Auto-generated method stub
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

}

取自here

Answer 4

以下是您可以替换的编辑代码，

public void quickSort(int[] a,int left, int length) {

           if(left >= length) return;
            int index = partition(a,left,length);
            if (left < index)
                quickSort(a, left, index);      // left subarray
            if (length > index + 1)
                quickSort(a, index + 1, length);  
        }

        private  int partition(int[] arr,int l, int length) {
            // TODO Auto-generated method stub
            int pivot = arr[(l + length)/2];
            int left = l - 1;  // index going left to right
            int right = length + 1;   // index going right to left

            while (true) {
                do {
                    left++;
                } while (arr[left] < pivot);
                do {
                    right--;
                } while (arr[right] > pivot); 

                if (left < right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                }
                else
                    return right;   // index of last element in the left subarray
            }    
        }

快速排序是一种分而治之的算法。它首先将一个大列表分成两个较小的子列表，然后递归地对这两个子列表进行排序。如果我们想对一个数组进行排序而不需要任何额外的 space，快速排序是一个不错的选择。平均而言，时间复杂度为 O(n log(n)).

数组排序的基本步骤如下：

Select 一个枢轴，通常是中间那个从两端交换元素，使左边的所有元素都小于枢轴，右边的所有元素都大于枢轴递归排序左边部分和右边部分

Arrays.sort() Java 中的方法使用快速排序对基元数组进行排序，例如整数或浮点数数组，并使用 Mergesort 对对象进行排序，例如字符串数组。

QuickSort 给出不正确的排序顺序

QuickSort giving incorrect sorting order

java

quicksort