Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。

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

新人の私: どういう意味ですか?ここに書きますか？ （履歴書を指しながら）

面接官: はい

新人の私: いいえ

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

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

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

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

実は、クイックキューは簡単なのですが、手書きで書けない人も多いのではないでしょうか?難しいですか? いくつかの方法でその場で手書きできる人もたくさんいます。

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

口述筆記

」を準備しただけです。

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

背景

百科事典より:

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

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

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

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

中心的なアイデア:

まずシーケンスから基本番号として数値を取得し、次にサイズ分割を実行します;

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

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

導入事例

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

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

最初のパス:

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

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

下一步：

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

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

 

2. 快速排序法全流程

3.程式碼實作

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

import java.util.Arrays;

public class QuickSortDemo {
    //四个步骤：
    //1.比较startIndex和endIndex，更喜欢理解为校验
    //2.找出基准
    //3.左边部分排序
    //4.右边排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找出基准
            int partition = partition(arr, startIndex, endIndex);
            //分成两边递归进行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基准
    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比基准大，right比基准小，进行交换
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一轮完成，让left和right重合的位置和基准交换，返回基准的位置
        swap(arr, startIndex, left);
        return left;
    }

    //两数交换
    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);
        //输出结果
        System.out.println(Arrays.toString(a));
    }
}

輸出結果：

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

程式碼實現，建議結合前面的動圖，理解起來就更簡單了。

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

4.複雜度分析

#時間複雜度：

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

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

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

（遞迴演算法的時間複雜度公式：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)的，也就是個常數級；而真正消耗空間的就是遞歸呼叫了，因為每次遞歸就要保持一些資料：

最優的情況下空間複雜度為:

O(log2n)

；每次都平分數組的情況最差的情況下空間複雜度為：

O( n )

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

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

5. 快速排序法總結

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

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

#

以上がMeituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。