java如何實現快速排序

這篇文章運用簡單易懂的例子給大家介紹java如何實現快速排序，代碼非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

快速排序又稱分區交換排序（partition-exchange sort），簡稱快排，一種排序算法。

在平均狀況下，排序n個項目要O(nlog n)（大O符號）次比較。在最壞狀況下則需要 O(n^2)次比較，但這種狀況并不常見。事實上，快速排序O(nlog n)通常明顯比其他算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地達成。

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然后遞歸地排序兩個子序列。

步驟為：

• 挑選基準值：從數列中挑出一個元素，稱為“基準”（pivot）。

• 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數可以到任何一邊）。在這個分割結束之后，對基準值的排序就已經完成。

• 遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。

遞歸到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序。

選取基準值有數種具體方法，此選取方法對排序的時間性能有決定性影響。

代碼實現：

 public class QuickSort {
    public static void main(String[] args) {
        int[] arr = SortUtil.randomArr(6);
        SortUtil.printArr(arr);
//        sort(arr,0,arr.length-1);
        sort1(arr,0,arr.length-1);
//        int[] arr1= netherlands(arr,0,arr.length-1);
//        SortUtil.printArr(arr1);
        SortUtil.printArr(arr);
    }
 
    /**
     * 快排1.0，時間復雜度O（n2），找出以arr[right]為界的中間位置，小于等于的放左邊，大于等于的放右邊
     * 分為左右2個區域，每個區域重復上面的步驟，直到最后left=right
     * @param arr
     * @param left
     * @param right
     */
    public static void sort(int[] arr,int left,int right){
        if(left>=right){return;}
        int mid = partition(arr,left,right);
        sort(arr,left,mid-1);
        sort(arr,mid+1,right);
    }
 
    /**
     * 快排2.0 以arr[right]作為中間值，最差情況時間復雜度O（n2），平均時間復雜度為 O(n logn) 
     * @param arr
     * @param left
     * @param right
     */
    public static void sort1(int[] arr,int left,int right){
        if(left>=right){return;}
        int[] mid = netherlands(arr,left,right);
        sort1(arr,left,mid[0]-1);
        sort1(arr,mid[1]+1,right);
    }
 
    private static int partition(int[] arr, int left, int right) {
        if (left > right) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int lessEqual = left - 1;
        int index = left;
 
        while (index < right) {
            // 情況1,當前位置小于等于標記值，當前位置不動，標記右移
            if (arr[index] <= arr[right]) {
                lessEqual++;
                // 擴大小于等于區域
                SortUtil.swap(arr, index, lessEqual);
            }
            index++;
        }
        // 右邊界位置和大于區域的起始位置交換
        SortUtil.swap(arr, ++lessEqual, right);
        return lessEqual;
    }
 
    /**
     * 荷蘭國旗問題
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int[]  netherlands(int[] arr,int left,int right){
        if(left>right){
            return new int[]{-1,-1};
        }
        if(left==right){
            return new int[]{left,right};
        }
        int lessEqual = left-1;
        int i = left;
        int more = right;
        while (i<more){
            // 1.i位置==arr[right],i++
            if (arr[i]==arr[right]){
                i ++;
            }
            // 2.i位置<arr[right],i位置與小于區域右一個位置交換
            else if (arr[i]<arr[right]){
                SortUtil.swap(arr,++lessEqual,i++);
            }
            // 3.i位置>arr[right],i位置與大于區域左一個位置交換，i不動
            else if(arr[i]>arr[right]){
                SortUtil.swap(arr,i,--more);
            }
        }
        SortUtil.swap(arr,right,more);
        return new int[]{lessEqual+1,more};
    }
 
}

關于java如何實現快速排序就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。