[[420688]]

面試官：我們繼續來聊聊關于數據結構與算法，你能寫一個快速排序?(說話的同時，把我簡歷反過來，遞給我一支筆，意思就是叫我在自己的簡歷背后寫)

菜鳥我：什么意思?這里寫嗎?(指著簡歷)

面試官：嗯

菜鳥我：不會

面試官：好吧，今天面試就到這里

菜鳥我：(心里很火，勞資的簡歷，想在勞資簡歷上寫代碼?)沙雕

面試官：(回頭看了一眼，一臉懵逼)

想想自己還是太年輕了，換著是現在就不是這樣了。寫就寫嘛，反正不就是一張紙而已。圖片

其實，快排說簡單嘛，估計很多人也手寫不出來，說難嗎也有很多人你能現場手寫幾種方式。

菜鳥我，當年還是能手寫一種，畢竟面試前我剛好刻意的準備過“默寫快排”。

下面，我們就來分析分析----快速排序。

背景

來自百科：

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以[遞歸]進行，以此達到整個數據變成有序序列。

這概念理解起來 還是蠻費勁兒的。

可以這么理解：

快速排序是冒泡排序的改進版，整個過程就在拆拆補補，東拆西補或西拆東補，一邊拆一邊補，直到所有元素達到有序狀態。

核心思想：

先從數列中取出一個數作為基準數，然后進行大小分區;

分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊;

再對左右區間重復第二步，直到各區間只有一個數，排序完成。

實現案例

下面先通過圖文形式一步一步進行拆解。

拿[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

所以平均時間復雜度為O(nlog2n)

空間復雜度：

快速排序使用的空間是O(1)的，也就是個常數級;而真正消耗空間的就是遞歸調用了，因為每次遞歸就要保持一些數據：

最優的情況下空間復雜度為:O(log2n);每一次都平分數組的情況

最差的情況下空間復雜度為：O( n );退化為冒泡排序的情況

所以平均空間復雜度為O(log2n)

5. 快速排序法總結

默認取第一個元素為軸心點(軸心點的確認區分了 “快速排序法”和“隨機排序法”)兩種算法，而隨機排序則隨機rand一個元素為軸心點;

如果兩個不相鄰元素交換，可以一次交換消除多個逆序，加快排序進程。

后記 

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