[[420688]]

面試官：我們繼續(xù)來(lái)聊聊關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法，你能寫一個(gè)快速排序?(說(shuō)話的同時(shí)，把我簡(jiǎn)歷反過(guò)來(lái)，遞給我一支筆，意思就是叫我在自己的簡(jiǎn)歷背后寫)

菜鳥(niǎo)我：什么意思?這里寫嗎?(指著簡(jiǎn)歷)

面試官：嗯

菜鳥(niǎo)我：不會(huì)

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

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

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

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

其實(shí)，快排說(shuō)簡(jiǎn)單嘛，估計(jì)很多人也手寫不出來(lái)，說(shuō)難嗎也有很多人你能現(xiàn)場(chǎng)手寫幾種方式。

菜鳥(niǎo)我，當(dāng)年還是能手寫一種，畢竟面試前我剛好刻意的準(zhǔn)備過(guò)“默寫快排”。

下面，我們就來(lái)分析分析----快速排序。

背景

來(lái)自百科：

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以[遞歸]進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

這概念理解起來(lái) 還是蠻費(fèi)勁兒的。

可以這么理解：

快速排序是冒泡排序的改進(jìn)版，整個(gè)過(guò)程就在拆拆補(bǔ)補(bǔ)，東拆西補(bǔ)或西拆東補(bǔ)，一邊拆一邊補(bǔ)，直到所有元素達(dá)到有序狀態(tài)。

核心思想：

先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)，然后進(jìn)行大小分區(qū);

分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊;

再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)，排序完成。

實(shí)現(xiàn)案例

下面先通過(guò)圖文形式一步一步進(jìn)行拆解。

拿[4,1,6,2,9,3]這個(gè)數(shù)組舉例。

第一遍遍歷：

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

目前數(shù)組順序?yàn)閇3，1，2，4，9，6]。

下一步：

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

右邊同理……避免視覺(jué)疲勞就不一一描述了，可看下面動(dòng)態(tài)演示圖。

2. 快速排序法全流程

3.代碼實(shí)現(xiàn)

下面，我們使用Java語(yǔ)言來(lái)實(shí)現(xiàn)前面的快排案例：

import java.util.Arrays; 
 
public class QuickSortDemo { 
    //四個(gè)步驟： 
    //1.比較startIndex和endIndex，更喜歡理解為校驗(yàn) 
    //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; 
         
        //等于就沒(méi)有必要排序 
        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] 

代碼實(shí)現(xiàn)，建議結(jié)合前面的動(dòng)圖，理解起來(lái)就更簡(jiǎn)單了。

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

4.復(fù)雜度分析

時(shí)間復(fù)雜度：

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

這種情況時(shí)間復(fù)雜度就好計(jì)算了，就是冒泡排序的時(shí)間復(fù)雜度：T[n] = n * (n-1) = n^2 + n;

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

(遞歸算法的時(shí)間復(fù)雜度公式：T[n] = aT[n/b] + f(n) )

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

所以平均時(shí)間復(fù)雜度為O(nlog2n)

空間復(fù)雜度：

快速排序使用的空間是O(1)的，也就是個(gè)常數(shù)級(jí);而真正消耗空間的就是遞歸調(diào)用了，因?yàn)槊看芜f歸就要保持一些數(shù)據(jù)：

最優(yōu)的情況下空間復(fù)雜度為:O(log2n);每一次都平分?jǐn)?shù)組的情況

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

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

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

默認(rèn)取第一個(gè)元素為軸心點(diǎn)(軸心點(diǎn)的確認(rèn)區(qū)分了 “快速排序法”和“隨機(jī)排序法”)兩種算法，而隨機(jī)排序則隨機(jī)rand一個(gè)元素為軸心點(diǎn);

如果兩個(gè)不相鄰元素交換，可以一次交換消除多個(gè)逆序，加快排序進(jìn)程。

后記 

最后再說(shuō)說(shuō)，其實(shí)你覺(jué)得快速排序在工作中有用嗎?工作近十年的我真的沒(méi)用過(guò)，但我知道這個(gè)快排的思路。如果面試前不準(zhǔn)備，我反正是肯定寫不出來(lái)的，你呢?