今天，這個(gè)題目是當(dāng)時(shí)面試官叫我現(xiàn)場(chǎng)手寫(xiě)快排，場(chǎng)景如下：

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

菜鳥(niǎo)我：什么意思？這里寫(xiě)嗎？（指著簡(jiǎn)歷）

面試官：嗯

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

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

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

面試官：（回頭看了一眼，一臉懵逼）

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

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

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

下面，我們就來(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)單了。

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

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)備，我反正是肯定寫(xiě)不出來(lái)的，你呢？