クイック ソートは、パーティション交換ソート (パーティション交換ソート) とも呼ばれ、クイック ソート、ソート アルゴリズムと呼ばれます。

(推奨チュートリアル: java 學(xué)習(xí) Web サイト)

平均的な狀況では、n 個の項目を並べ替えるには O(nlog n) (大きな O 表記) の比較が必要です。最悪の場合、O(n^2) 個の比較が必要になりますが、この狀況は一般的ではありません。実際、クイックソート O(nlog n) は、ほとんどのアーキテクチャで內(nèi)部ループを効率的に実現(xiàn)できるため、通常、他のアルゴリズムよりも大幅に高速です。

クイック ソートでは、分割統(tǒng)治戦略を使用してシーケンス (リスト) を 2 つのサブシーケンス (小さい方と大きい方) に分割し、その 2 つのサブシーケンスを再帰的に並べ替えます。

手順は次のとおりです:

• ピボット値を選択します。シーケンスから「ピボット」と呼ばれる要素を選択します。

• 分割: シーケンスを並べ替えます。ベースライン値より小さいすべての要素はベースラインの前に配置され、ベースライン値より大きいすべての要素はベースラインの後ろに配置されます (數(shù)値はベースラインの後ろに配置されます)。ベースライン値はどちらの側(cè)でも構(gòu)いません)。この分割が完了すると、基準(zhǔn)値の並べ替えが完了する。

• サブシーケンスを再帰的に並べ替える: ベースライン値より小さい要素を持つサブシーケンスと、ベースライン値より大きい要素を持つサブシーケンスを再帰的に並べ替えます。

最下位再帰の判定條件は、配列のサイズが0か1であることですが、このとき配列は當(dāng)然整っています。

(ビデオチュートリアルの推奨: java 學(xué)習(xí))

ベンチマーク値を選択するにはいくつかの具體的な方法があります。この選択方法は、ソートの時間パフォーマンスに決定的な影響を與えます。 。

コード実裝:

 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，時間復(fù)雜度O（n2），找出以arr[right]為界的中間位置，小于等于的放左邊，大于等于的放右邊
     * 分為左右2個區(qū)域，每個區(qū)域重復(fù)上面的步驟，直到最后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]作為中間值，最差情況時間復(fù)雜度O（n2），平均時間復(fù)雜度為 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,當(dāng)前位置小于等于標(biāo)記值，當(dāng)前位置不動，標(biāo)記右移
            if (arr[index] <= arr[right]) {
                lessEqual++;
                // 擴(kuò)大小于等于區(qū)域
                SortUtil.swap(arr, index, lessEqual);
            }
            index++;
        }
        // 右邊界位置和大于區(qū)域的起始位置交換
        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位置與小于區(qū)域右一個位置交換
            else if (arr[i]<arr[right]){
                SortUtil.swap(arr,++lessEqual,i++);
            }
            // 3.i位置>arr[right],i位置與大于區(qū)域左一個位置交換，i不動
            else if(arr[i]>arr[right]){
                SortUtil.swap(arr,i,--more);
            }
        }
        SortUtil.swap(arr,right,more);
        return new int[]{lessEqual+1,more};
    }
 
}

以上がJavaでクイックソートを?qū)g裝する（コード例）の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。