面接現場:手書きクイックソートアルゴリズム

アルゴリズムの概要
高速ソート(Quicksort)は、分割交換ソートとも呼ばれ、高速ソートと略称され、ソートアルゴリズムであり、最も早く東尼・ホールによって提案された.平均では,n個の項目を並べ替えてO(n log n)回比較する.最悪の場合はO(n^2)回の比較が必要であるが,このような状況はあまり見られない.
実際,高速ソートO(n log n)は通常,その内部サイクルが大部分のアーキテクチャで効率的に達成できるため,他のアルゴリズムよりも明らかに速い.
アルゴリズムフロー
クイックソートは、分割ポリシーを使用して、1つのシーケンスをより小さい2つのサブシーケンスとより大きい2つのサブシーケンスに分割し、2つのサブシーケンスを再帰的にソートします.
手順は次のとおりです.

選択基準値:数列から1つの要素を選択し、「基準」(pivot)、

と呼ぶ.

分割:数列を並べ替え、基準値より小さいすべての要素を基準の前に配置し、基準値より大きいすべての要素を基準の後ろに配置します(基準値と等しい数はいずれの側にもできます).この分割が終了すると、基準値の並べ替えが完了し、

再帰ソートサブシーケンス:基準値要素より小さいサブシーケンスと基準値要素より大きいサブシーケンスを再帰的にソートします.

最下部に再帰される判断条件は、数列の大きさがゼロまたは1であることであり、このとき、数列は明らかに秩序化されている.
基準値を選択するには、ソートの時間的パフォーマンスに決定的な影響を与えるいくつかの具体的な方法があります.
アルゴリズムステップ
クイックソートのアルゴリズム手順を5ステップに分けます.

public void quick(int arr, int head, int tail) {
    /*
    * 1.      
    * 2.          
    * 3.           ，           
    * 4.       
    * 5.       
    */
}

サンプルコード

public class QuickSort {
  
    public static void qSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        //          
        int left = head;
        int right = tail;
        int pivot = arr[head]; //   ，   arr[(head + tail) / 2]

        while (left <= right) {
            while (arr[left] < pivot) { //     ，            
                ++left;
            }
            while (arr[right] > pivot) { //     ，            
                --right;
            }
            if (left < right) {
                //  arr[left] arr[right]   
                int t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
                //    
                ++left;
                --right;
            } else if (left == right) {
                //   ，     
                ++left;
                //break;
            }
        }

        qSort(arr, head, right);
        qSort(arr, left, tail);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        qSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
  
}

印刷出力:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

プログラム実行では、ソート前とソート後の数列を印刷して実行フローを観察できます.

    [6 1 2 7 9 3 4 5 10 8 ]   ，     [5 1 2 4 3 9 7 (6) 10 8 ] 
    [5 1 2 4 3 ]   ，     [3 1 2 4 (5) 9 7 6 10 8 ] 
    [3 1 2 4 ]   ，     [2 1 (3) 4 5 9 7 6 10 8 ] 
    [2 1 ]   ，     [1 (2) 3 4 5 9 7 6 10 8 ] 
    [3 4 ]   ，     [1 2 (3) 4 5 9 7 6 10 8 ] 
    [9 7 6 10 8 ]   ，     [1 2 3 4 5 8 7 6 10 (9) ] 
    [8 7 6 ]   ，     [1 2 3 4 5 6 7 (8) 10 9 ] 
    [6 7 ]   ，     [1 2 3 4 5 (6) 7 8 10 9 ] 
    [10 9 ]   ，     [1 2 3 4 5 6 7 8 9 (10) ] 

複雑度分析
時間の複雑さ
配列にはn個の要素があり、再帰演算するために支点pivotの位置を算出し、再帰的に左半分と有半分を呼び出す.このとき理解上は第1層であればn/2、n/2、第2層であればn/4、n/4、n/4、n/4の4つの部分、すなわちn個の要素理解上は全部で2^k=n、k=log 2(n)であり、そして各層はnの複雑さである.平均はO(nlog 2 n)の時間的複雑さである.しかし、これは平均的な状況に違いありません.もしあなたが標準的なソートの場合、すでに昇順の順序であれば、再帰は右半分しか存在せず、左半分は淘汰されました.(n-1)(n-2)....*1,この複雑さはOに違いない(n^2).
くうかんふくざつさ
高速列の実装は再帰的に呼び出され、関数呼び出しのたびに定数の空間しか使用されないため、空間複雑度は再帰深さに等しい.
最良の場合、最大O(log 2 n)回のネスト再帰呼び出しが必要であるため、O(log 2 n)の空間が必要である.最悪の場合,O(n)サブネスト再帰呼び出しが必要であるため,O(n)の空間が必要である.
時間の複雑さは自知を引用する
https://www.zhihu.com/question/22393997/answer/189896378