排序算法：快速排序

微信搜尋【程式員囧輝】，關注這個堅持分享技術幹貨的程式員。

我的最新文章：BAT 老兵的經驗之談，成長路上這個道理越早知道越好

概述

手寫排序算法幾乎是程式員面試必問的題目，大多數人都會選擇寫冒泡排序，如果此時你寫的是其他改進過的排序算法，相信會讓面試官眼前一亮。本文将介紹常見的排序算法中的“快速排序”。

基本思想

快速排序（QuickSort）是對冒泡排序的一種改進。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：

1. 從要排序的資料中取一個數為“基準數”。
2. 通過一趟排序将要排序的資料分割成獨立的兩部分，其中左邊的資料都比“基準數”小，右邊的資料都比“基準數”大。
3. 然後再按步驟2對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

該思想可以概括為：挖坑填數 + 分治法。

分治法

分治，字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。在計算機科學中，分治法就是運用分治思想的一種很重要的算法。分治法是很多高效算法的基礎，如快速排序，歸并排序，傅立葉變換（快速傅立葉變換）等等。

例子

下面通過一個例子來看看快速排序是怎麼工作的，例子中表格中紅色的字型為需要填的坑，綠色的字型為已經移動過的資料。

1）剛開始，i 和 j 分别指向數組頭和數組尾，即 i = 0，j = 9，基準數取第一個數，即 index = array[i] = array[0] = 23。

此時，array[0] 的值已經存在了index，是以 array[0] 的位置就好像被挖了個坑，可以填充一個數。

是以，我們從位置 j 開始向左尋找比 index 小的數，當 j = 8 時，符合條件，于是我們将 array[8] 的值填到 array[0] ，即将 9 填入 array[0]，并将 i 向右移動一個位置，即 i++。

從位置 j 向左尋找比 index 小的數，并在尋找到後填入坑中，用代碼表示如下。

while (i < j && array[j] >= index) { // 向左尋找第一個小于index的數
    j--;
}
if (i < j) {
    array[i++] = array[j]; // 将array[j]填入array[i]，并将i向右移動
}
           

此時，array 數組如下圖。

2）因為 array[0] 的坑被 array[8] 填了，于是 array[8] 的位置又成了一個新的坑。此時我們從位置 i 開始向右尋找比 index 大的數，當 i = 2 時符合條件，于是我們将 array[2] 的值填到 array[8] ，即将 37 填入 array[8]，并将 j 向左移動一個位置，即 j--。

從位置 i 向右尋找比 index 大的數，并在尋找到後填入坑中，用代碼表示如下（跟上面相似）。

while (i < j && array[i] < index) {// 向右尋找第一個大于index的數
    i++;
}
if (i < j) {
    array[j--] = array[i]; // 将array[i]填入array[j]，并将j向左移動
}
           

此時，array 數組如下圖。

以之後重複上述過程即可。

3）同樣的，array[8] 的坑被 array[2] 填了，于是 array[2] 的位置又成了一個新的坑。此時我們從位置 j 開始向左尋找比 index 小的數，當 j = 5 時符合條件，于是我們将 array[5] 的值填到 array[2] ，即将 21 填入 array[2]，并将 i 向右移動一個位置，即 i++，此時 array 數組如下圖。

4）同樣的，array[2] 的坑被 array[5] 填了，于是 array[5] 的位置又成了一個新的坑。此時我們從位置 i 開始向右尋找比 index 大的數，當 i = 3 時符合條件，于是我們将 array[3] 的值填到 array[5] ，即将 89 填入 array[5]，并将 j 向左移動一個位置，即 j--，此時 array 數組如下圖。

5）同樣的，array[5] 的坑被 array[3] 填了，于是 array[3] 的位置又成了一個新的坑。此時我們從位置 j 開始向左尋找比 index 小的數，當 j = 4 時符合條件，于是我們将 array[4] 的值填到 array[3] ，即将 2 填入 array[3]，并将 i 向右移動一個位置，即 i++，此時 array 數組如下圖。

6）此時，我們發現 i = j，結束周遊，并将index填入 array[4]，即将 23 填入 array[4]，此時 array 數組如下圖。此時，array[4] 左邊的資料全比 array[4] 小，而 array[4] 右邊的資料全比 array[4] 大。

7）接下去，我們隻需要對 array[4] 兩邊的資料分别在進行上面的操作即可（分治法），如下圖。

分治的代碼可以寫成如下：

quickSort(array, low, i - 1); // 遞歸調用，分治
quickSort(array, i + 1, high); // 遞歸調用，分治
           

整合

根據以上步驟，稍微整理一下，可以得出快速排序的代碼如下：

public class QuickSort {
    private static void quickSort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = low, j = high, index = array[i]; // 取最左邊的數作為基準數
        while (i < j) {
            while (i < j && array[j] >= index) { // 向左尋找第一個小于index的數
                j--;
            }
            if (i < j) {
                array[i++] = array[j]; // 将array[j]填入array[i]，并将i向右移動
            }
            while (i < j && array[i] < index) {// 向右尋找第一個大于index的數
                i++;
            }
            if (i < j) {
                array[j--] = array[i]; // 将array[i]填入array[j]，并将j向左移動
            }
        }
        array[i] = index; // 将基準數填入最後的坑
        quickSort(array, low, i - 1); // 遞歸調用，分治
        quickSort(array, i + 1, high); // 遞歸調用，分治
    }

    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }
}
           

時間複雜度

最好情況的時間複雜度為O(nlogn)，過程比較複雜，就不在此贅述。

最差情況下每一次取到的數（基準數）都是目前要比較的數中的最大/最小值，在這種情況下，每次都隻能得到比上一次少1個數的子序列（即要麼全比基準數大，要麼全比基準小），此時相當于一個冒泡排序，比較的次數 = (n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2，此時的時間複雜度為：O(n^2)。最差情況一般出現在：待排序的資料本身已經是正序或反序排好了。

使用場景

基本上在任何需要排序的場景都可以使用快速排序。雖然快速排序的最壞情況時間複雜度為O(n^2)，但是由于基本不會出現，是以可以放心的使用快速排序。在本人的電腦測試，100萬的随機數字，快速排序大約耗時120毫秒。

最後

了解了快速排序的基本思想後，手寫快速排序算法就變得沒那麼難了，隻需要多練習幾遍，相信在面試中手寫快速排序算法便是小菜一碟。

推薦閱讀

Java 基礎高頻面試題（2021年最新版）

921天，鹹魚到阿裡的修仙之路

兩年Java開發工作經驗面試總結

4 年 Java 經驗，阿裡網易拼多多面試總結、心得體會

5 年 Java 經驗，位元組、美團、快手核心部門面試總結（真題解析）

如何寫一份讓 HR 眼前一亮的履歷（附模闆）

面試阿裡，HashMap 這一篇就夠了

面試必問的 MySQL，你懂了嗎？

面試必問的線程池，你懂了嗎？

跳槽，如何選擇一家公司

如何準備好一場大廠面試

MySQL 8.0 MVCC 核心原了解析（核心源碼）

複習2個月拿下美團offer，我都做了些啥