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

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

菜鳥我：什么意思？這里寫嗎？（指著簡歷）

面試官：嗯

菜鳥我：不會

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

菜鳥我：（心里很火，勞資的簡歷，想在勞資簡歷上寫代碼？）沙雕

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

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

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

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

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

背景

來自百科：

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

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

可以這么理解：

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

核心思想：

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

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

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

實現(xiàn)案例

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

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

第一遍遍歷：

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

目前數(shù)組順序為[3，1，2，4，9，6]。

下一步：

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

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

?

2. 快速排序法全流程

3.代碼實現(xiàn)

下面，我們使用Java語言來實現(xiàn)前面的快排案例：

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);
            //分成兩邊遞歸進行
            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)小，進行交換
            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.復(fù)雜度分析

時間復(fù)雜度：

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

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

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

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

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

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

空間復(fù)雜度：

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

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

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

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

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

• 默認取第一個元素為軸心點（軸心點的確認區(qū)分了 “快速排序法”和“隨機排序法”）兩種算法，而隨機排序則隨機rand一個元素為軸心點；
• 如果兩個不相鄰元素交換，可以一次交換消除多個逆序，加快排序進程。

后記

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