今日は、この質(zhì)問を面接官がその場で手書きで手早く整理してもらいました。 : チャットを続けましょう。データ構(gòu)造とアルゴリズムについて、簡単なソートを書いてもらえますか? （話している間、彼は私の履歴書をひっくり返してペンを渡しました。つまり、履歴書の裏に書くように言われました）

面接官: はい

新人の私: いいえ

面接官: はい、今日の面接はこれで終わりです

新人の私: (とても怒っています。これは労使の履歴書です。労使の履歴書にコードを書きますか?) Shadiao

インタビュアー: (振り返り、混亂して)

よく考えたらまだ若かったけど、今はそんなことはないでしょう。とにかく書くだけ、それはただの紙切れです。

私は初心者ですが手書きはできるので、面接前に意図的に「

」を準(zhǔn)備しただけです。

次に分析分析----クイックソートを行っていきます。

百科事典より:

クイック ソートは、1962 年に C. A. R. Hoare によって提案されました。その基本的な考え方は、1 回の並べ替えで並べ替え対象のデータを 2 つの獨立した部分に分割することです。一方の部分のすべてのデータは、もう一方の部分のすべてのデータよりも小さいため、この方法を使用して、データの 2 つの部分をすばやく分離します。並べ替えでは、並べ替えプロセス全體を [再帰的に ] 実行できるため、データ全體が順序付けされたシーケンスになります。

この概念を理解するのは非常に困難です。

これは次のように理解できます:

クイック ソートはバブル ソートの改良版です。全體のプロセスは、物事をばらばらにしてつなぎ合わせることです。すべての要素は順序付けられた狀態(tài)に達(dá)します。

中心的なアイデア:

まずシーケンスから基本番號として數(shù)値を取得し、次にサイズ分割を?qū)g行します;

分割プロセス中に、この數(shù)値を比較します。大きい數(shù)値をすべて右側(cè)に配置し、それ以下の數(shù)値をすべて左側(cè)に配置します。

各間隔に數(shù)値が 1 つだけになるまで、左右の間隔に対して 2 番目のステップを繰り返します。 , これで並び替えは完了です。

導(dǎo)入事例

以下は、寫真の形式で段階的に分解したものです。そしてテキスト。

配列 [4,1,6,2,9,3] を例として取り上げます。

最初のパス:

• 先進(jìn)行拆分[4,1,6,2,9,3] 選擇元素4 為軸心點
• 檢查是否1 < 4 (軸心點)
• 檢查是否6 < 4 (軸心點)
• 檢查是否2 < 4 (軸心點)
• 2 < 4 (軸心點) 是為真，將指數(shù)2和儲存指數(shù)6 進(jìn)行交換
• ##檢查是否9 < 4 (軸心點)
• 檢查是否3 < 4 (軸心點)
• 3 < 4 (軸心點) 為真，將指數(shù)3和儲存指數(shù)6 進(jìn)行交換
• 將軸心點4和儲存指數(shù)3進(jìn)行交換
• 此時軸心點4左邊全部小於4，右邊大於4

#目前陣列順序為[3，1，2，4，9， 6]。

下一步：

• 先將左邊先排好序
• 選擇元素3 為軸心點
• 檢查是否1 < 3 (軸心點)
• #檢查是否2 < 3 (軸心點)
• 將軸心點3和儲存指數(shù)值2進(jìn)行交換
• 現(xiàn)在軸心點已經(jīng)在排序後的位置
• #進(jìn)行分割[2,1] 選擇2 為軸心點
• 檢查是否1 < 2 (軸心點)
• 左邊遍歷完成，將軸心點2和儲存指數(shù)1 進(jìn)行交換

右邊同理…避免視覺疲勞就不一一描述了，可看下面動態(tài)示範(fàn)圖。

?

2. 快速排序法全流程

3.程式碼實作

下面，我們使用Java語言來實作前面的快排案例：

import java.util.Arrays;

public class QuickSortDemo {
    //四個步驟：
    //1.比較startIndex和endIndex，更喜歡理解為校驗
    //2.找出基準(zhǔn)
    //3.左邊部分排序
    //4.右邊排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找出基準(zhǔn)
            int partition = partition(arr, startIndex, endIndex);
            //分成兩邊遞歸進(jìn)行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基準(zhǔn)
    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        
        int left = startIndex;
        int right = endIndex;
        
        //等于就沒有必要排序
        while (left != right) {
            
            while (left < right && arr[right] > pivot) {
                right--;
            }
          
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //找到left比基準(zhǔn)大，right比基準(zhǔn)小，進(jìn)行交換
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一輪完成，讓left和right重合的位置和基準(zhǔn)交換，返回基準(zhǔn)的位置
        swap(arr, startIndex, left);
        return left;
    }

    //兩數(shù)交換
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2, 4, 9, 6};
        quickSort(a, 0, a.length - 1);
        //輸出結(jié)果
        System.out.println(Arrays.toString(a));
    }
}

輸出結(jié)果：

[1, 2, 3, 4, 6, 9]

程式碼實現(xiàn)，建議結(jié)合前面的動圖，理解起來就更簡單了。

快排寫法還有幾種，有興趣的可以自行找一下，另外也可以看看維基百科中，快排是怎麼介紹的。

4.複雜度分析

#時間複雜度：

最壞情況就是每一次取到的元素就是數(shù)組中最小/最大的，這種情況其實就是冒泡排序了(每一次都排好一個元素的順序)

這種情況時間複雜度就好計算了，就是冒泡排序的時間複雜度：T[n] = n * (n-1) = n^2 n;

最好情況下是O(nlog2n)，推導(dǎo)過程如下：

（遞迴演算法的時間複雜度公式：T[n] = aT[n/b] f(n) ?）

https://img2018.cnblogs.com/blog/1258817/201903/1258817-20190326191158640-601403776.png

所以#nlogn##所以#nlogn#（所以#nlog2）##n#nlogn#n#n#n#n#2）#n#n#n#n#2）#n#nlogn#（所以#nlogn.

空間複雜度：

快速排序使用的空間是O(1)的，也就是個常數(shù)級；而真正消耗空間的就是遞歸呼叫了，因為每次遞歸就要保持一些資料：

最優(yōu)的情況下空間複雜度為:

O(log2n)

；每次都平分?jǐn)?shù)組的情況最差的情況下空間複雜度為：

O( n )

；退化為冒泡排序的情況所以

平均空間複雜度為O（log2n）

5. 快速排序法總結(jié)

#預(yù)設(shè)取第一個元素為軸心點（軸心點的確認(rèn)區(qū)分了「快速排序法」和「隨機(jī)排序法」）兩種演算法，而隨機(jī)排序則隨機(jī)rand一個元素為軸心點；
如果兩個不相鄰元素交換，可以一次交換消除多個逆序，加快排序進(jìn)程。

後記 最後再說說，其實你覺得快速排序在工作上有用嗎？工作近十年的我真的沒用過，但我知道這個快排的想法。如果面試前不準(zhǔn)備，我反正是肯定寫不出來的，你呢？

#