前言

本文主要介紹基于比較的七種常見排序演算法，分別為：選擇排序法，插入排序法，希爾排序法，冒泡排序法，堆排序法，歸并排序法，快速排序法，

基于比較的排序演算法是指對于元素的排序必須是建立在元素之間是可以比較的，體現在 j a v a java java??? 語言中為待排序的元素型別是實作了 C o m p a r a b l e Comparable Comparable????? 介面的型別，

本文所涉及的復雜度分析都是基于現有結論加上自己的簡單的理解，所以可能非常不嚴謹，大家看看就好，不過最終的結論都是對的，

在分析復雜度的同時也對排序演算法的穩定性進行了分析，下面先對排序演算法的穩定性先做一些簡單的解釋，

排序演算法的穩定性

在一組資料中，排序前相等的兩個元素，在排序后相對的位置不變，這樣的排序演算法就被稱為穩定的排序演算法，

如果排序的元素只存在一個資料域(屬性)，那么對于排序演算法的穩定性可以沒有太高的要求，但是排序的元素如果超過一個資料域，對于排序演算法的穩定性可能就有要求了，

例如：對于一組學生的成績進行降序排列，學生不僅有成績這一個屬性還有學生姓名等其它屬性，那么在排列的程序中對于成績相同的學生而言，最終的排列次序就取決于排序演算法的穩定性，

穩定的排序演算法可以 100 % 100\% 100%? 的保證每次排序的結果中相同元素的相對位置沒有發生任何變化，

不穩定的排序演算法不能 100 % 100\% 100% 的保證每次排序的結果中相同元素的相對位置沒有發生任何變化，

注： 本文中出現的所有動態圖片全部來自于：visualgo 這個網站，感興趣的同學可以瀏覽一下，網站中提供了大量資料結構相關的動態圖，并且還配有教程，十分不錯，

選擇排序

基本思路

選擇排序(Selection sort)，是最基礎的排序演算法之一，也是通常最容易想到的一種排序演算法，基本思路為對一組有 n n n??? 個元素的資料，每一輪都選擇一個最小(默認升序排列)的元素放置在待排序區間的第一個位置，經過 n ? 1 n - 1 n?1??????? 輪的選擇后，所有元素都被放置在它應該處于的位置，

代碼實作

具體實作上，需要使用兩層回圈來遍歷陣列每一個元素，外層回圈控制整個排序需要的輪數，定義外層回圈變數 i ，初始指向陣列第一個元素，也就是下標為 0 的元素，i 需要維護的回圈不變數為，每次進入回圈時 [0 , i - 1]區間為有序區間，[i, n - 1] 區間為無序區間(n 表示元素個數)，當 i == n - 1 時，無序區間只存在一個元素，而其它元素都是已經被放置它們最終的位置所以最后一個元素在整個陣列中也一定是有序的，此時可以排序完畢，退出整個回圈，

內層回圈負責在本輪回圈中到待排序區間找到最小元素并紀錄該元素的索引，定義內層回圈變數 j 用于掃描待排序區間的每一個元素，初始指向 i + 1的位置，i 進入回圈時指向待排序區間的第一個元素，用變數 min 紀錄 i 的位置，表示默認 i 索引上的元素為區間內的最小元素，j 通過掃描其后的所有元素與 min 上的元素比較，當發現存在小于 min 位置上的元素時，就將 min 的值更為較小值的索引 j，直到 j 遍歷完陣列最后一個元素時，退出內層回圈，當內層回圈結束時，將 min 索引上的最小元素與待排序區間第一個元素 (i 索引上的元素) 進行交換，

public class SelectionSort {

    /**
     * 選擇排序（升序）,  每一次遍歷都找到待排序元素中最小的一個元素,并將該元素放置在待排序元素的第一個位置，
     */
    public static <E extends Comparable<E>> void sort(E[] array) {
        int n = array.length;
        int min;  // min 記錄了每次內層回圈結束后待排序元素中最小元素的索引
        for (int i = 0; i < n - 1; i++) {
            min = i; // 將索引 i 的元素默認為本輪選擇排序的最小元素，

            for (int j = i + 1; j < n; j++) {  // 遍歷[i + 1, n) 區間元素，
                if (array[j].compareTo(array[min]) < 0) {  // 區間內發現比 arr[min] 更小的元素時
                    min = j; // 將 min 更新為 j
                }
            }
            if (min != i) {  // 內層回圈結束時, min != i 則說明 [i + 1, n)區間 存在更小的元素
                swap(array, i, min);  // 則交換2個索引上的元素
            }
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

復雜度分析

時間復雜度： O(n²)，每一輪比較確定一個元素的最終位置，也就是去掉一個待排序元素，直到待排序區間沒有元素時停止，那么第一輪需要掃描 n 個元素，第二輪掃描 n - 1，n - 2，n - 3 … 1 總共掃描 n(n - 1) / 2 次，所以時間復雜度為 O(n²)，

空間復雜度： O(1)，選擇排序不需要申請額外的內層空間進行輔助排序，不管資料規模多大，使用的輔助變數都說是固定的，因此空間復雜度為 O(1)，

穩定性： 選擇排序演算法是不穩定的排序演算法，假設當前未排序的第一個元素 a₁ 后存在一個相同的元素a₂，在 a₂ 之后存在一個未排序的最小元素 b₁ 那么當 a₁ 和 b₁ 交換位置后，a₁ 就位于了 a₂ 之后，所以選擇排序的交換是跳躍式的，會改變兩個相同元素間原本的位置關系，

插入排序

基本思想

插入排序(Insertion Sort)，也是一種基礎的排序演算法，其基本思想是將待排序區間中的一個元素插入到有序區間的合理位置上，使得有序區間內的元素增加，待排序區間中的元素減少，直到待排序區間沒有元素位置，

代碼實作

具體實作上，同樣需要兩個回圈解決問題(默認升序排列)，定義外層回圈變數 i 指向陣列中未排序區間的第一個元素，也就是本輪需要插入至有序區間中的元素，同時 i 需要維護的回圈不變數為每次進入回圈時 [0, i - 1] 為有序區間，[i, n - 1] 為無序區間(n 表示元素個數)，初始時，i = 0 表示有序區間沒有元素，每次進入外層回圈時，將 i 位置元素用臨時變數 temp 保存，用于與 i 之前的有序元素進行比較，

定義內層回圈變數 j，j 初始指向 i ，用于紀錄 temp 元素應該插入的位置，在記憶體回圈中每一次將 temp 與 j - 1 位置上的元素進行比較，如果 temp < j - 1 位置上的元素，那么 temp 就應該插入到 j - 1 位置，而 j - 1 位置的元素也應該后移到 j 位置上，這里直接將 j - 1 位置上的元素覆寫到 j 位置上，并用 j 來紀錄 temp 應該插入的位置，也就是 j = j - 1 ，因為 j 的指向已經前移，那么就繼續比較更新后j - 1 這個位置上的元素，如果 temp < j - 1位置上的元素，重復上述操作，直到 temp >= j - 1 位置上的元素，或者 j 將有序區間中所有元素都比較一遍( j == 0) 時退出內層回圈，此時 j 存盤的位置即為 temp 應該插入的位置，將 temp 插入到該位置即可，

重復上述操作，直到 i == n，也就是無序區間 [i, n - 1] 為空區間時，退出整個回圈，陣列排序完成，

代碼實作：

public class InsertionSort {
    public static <T extends Comparable<T>> void sort(T[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            T temp = arr[i];   // 保存待插入元素
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(temp) > 0; j--) { // 當j > 0 && j arr[j-1] > temp
                arr[j] = arr[j - 1];  // arr[j-1]的元素后移
            }
            // 當退出回圈時，arr[j]就是temp應該存入的位置
            arr[j] = temp;  // 將temp賦值給arr[j]
        }
    }
}

復雜度分析

時間復雜度： O(n²)，插入排序演算法在最壞情況下，也就是陣列完全逆序的情況下，后面的元素肯定小于前面的所有元素，所以每一輪待插入的元素對需要與有序區間內所有的元素進行比較，并最終插入到有序區間的第一個位置，當 i = 0 時，沒有有序元素進行比較，所以不會進入內層回圈，當 i = 1 時，有序區間存在一個元素，需要比較 1 次，并將索引 1 位置的元素放到索引 0 的位置上，那么當 i = 2 時，就需要比較 2 次，i = 3，比較 3 次，一直到 i = n - 1 需要比較 n - 1 次，所以總共比較的次數為 1 + 2 + 3 + … + n - 1 = n(n - 1)/2，那么最壞時間復雜度為 O(n²)，而一般普通演算法的時間復雜度都是取最壞時間復雜度，所以插入排序的時間復雜度為 O(n²)，

不過需要注意的是，插入排序在完全有序的情況下，時間復雜度可以達到 O(n) 級別，不難理解，當待排序元素與前一個元素進行比較時，前一個元素一定是小于待排序元素的，因此每輪的內層回圈只執行了一次，所以總的時間復雜度為 O(n)，而一般而言，資料規模越小時，資料有序的可能性越大，并且插入排序所要比較的次數也越少，所以插入排序經常被用于高級排序演算法的優化，用于處理小規模資料時的排序作業，

空間復雜度： O(1)， 原地排序演算法，

穩定性：插入排序法是穩定的排序演算法，假設 a₁ 為未排序的元素，如果之前存在相同元素 a₂，那么 a₁ 是不會插入到 a₂ 之前的，這是因為 a1 會逐個向前與元素進行比較，當遇到 a₂時根據插入排序的比較邏輯就會停在 a₂ 的后一個位置，這樣就保證了2個元素的相對位置不會發生改變，

不過將如果將內層回圈的比較邏輯改成包含等于的情況，那么插入排序法也會變成不穩定的排序演算法，所以對于穩定的排序演算法而言，它是可以被修改為不穩定的排序演算法，但是對于不穩定的排序演算法而言，無論怎樣修改都不能成為穩定的排序演算法，

希爾排序

基本思想

希爾排序(Shell Sort)是對插入排序演算法的優化，在介紹插入排序時提到過插入排序演算法在資料完全有序或者基本有序的情況下時間復雜度可以達到 O(n) 級別，而一般來說資料規模越小時，資料有序的可能性越大，不過在實際的應用中一組資料的排列不可能以我們想要的方式呈現，而希爾排序演算法就是為了創造這些條件而誕生的，其基本思想為：讓待排序的資料變得越來越有序，

代碼實作

具體實作是將一組資料分成若干個子序列，對每一個子序列進行插入排序，那么經過這一輪排序過后，整組資料就比之前變得更加有序，接著再進行下一輪的排序，繼續將整組資料分成若干個子序列不過這一次的分組數量要小于上一次的分組數量，當整組陣列基本有序時，最后再將整組資料看成一組進行插入排序，操作結束后整組資料也就排序完畢，

需要注意的是，所謂的基本有序是指在一組資料中，較小的元素都在靠前的位置，較大的元素都在靠后的位置，而不大不小的元素都在靠中間的位置，所以，對于一組資料的分組并不是將一段連續的子序列劃分為一組，因為這樣劃分后每個子序列在進行插入排序后，所移動的空間是有限的，無法使得原本靠前的較大元素移動到靠后的位置，同樣也無法將原本靠后的較小元素移動到較大的位置，

為了達到整組陣列越來越有序，正確的分組方式是將整組資料里相距為某個增量的元素劃分為一組子序列，這樣在對每一個子序列進行插入排序時，如果兩個相差一個增量的元素間存在逆序關系，在進行插入時逆序元素的移動范圍也會更大，也就更加靠近它應該處于的范圍，最終陣列資料也會變的越來越有序，

增量的選擇決定了每一輪希爾排序時，資料被劃分為了多少組，同時增量的選擇也會影響希爾排序的性能，增量的選擇目前還沒有得到一個最優解，這屬于計算機科學界未解的一個難題，常用的增量選擇每次為原增量的 1/2，或者是每次取原增量的 1/3 + 1，這里以取原增量的 1/2 舉例：

首次選擇的增量為整組資料 n 的一半，也就是 n/2，那么整組資料也就被劃分為了 n / 2組，其中每一組中有兩個元素，對這 n / 2 組資料進行插入排序后，下一次的增量為 n / 4 ，n / 8，…，一直到 1 ，最后一次增量值必須唯一，也就是將整組資料劃分為 1 組進行插入排序，

其實大體的邏輯與插入排序基本一致，主要是每輪插入排序后需要更新增量為之前的一半，并且比較前一個元素元素不是固定為 -1 位置上的元素，而是減去增量后位置上的元素，

具體程序如下圖：

代碼實作：

public class ShellSort {   
	public static <E extends Comparable<E>> void sort(E[] array) {
        if (array == null)
            return;
        int n = array.length;
        int gap = n / 2;    // 初始增量為 n/2
        while (gap >= 1) {  
            for (int i = gap; i < n; i++) {   // i 等于初始增量
                E t = array[i];     // 保存要插入到前面有序區間的元素
                int j = i;
                for (; j - gap >= 0 && array[j - gap].compareTo(t) > 0; j -= gap) {  // j 每一步的偏移量為 gap 
                    array[j] = array[j - gap];
                }
                array[j] = t;
            }
            gap = gap / 2;  // 本輪插入排序完畢后, 縮小增量繼續下一輪插入排序, 直到 gap < 0
        }
    }
}

復雜度分析

時間復雜度： O(nlogn) ~ O(n²)，希爾排序的性能取決于增量的設定單從代碼層面來看它的時間復雜度應該是 O(n²)，但是實際上要比 *O(n²)*快上許多，在我的電腦上測驗資料規模 10 萬可以和 O(nlogn) 的排序演算法性能接近，對于百萬級規模的資料，也能在 2s 之內完成排序，所以它的時間復雜度應該是介于 O(nlogn) ~ O(n² ，不過對于希爾排序的具體時間復雜度分析非常復雜，也超過了博主的能力范圍，因此這里只是給出了一個大概的范圍，有些書上也會說，在取特定的增量時，希爾排序的時間復雜度在 O(n^1.3) 左右，這里了解即可，

空間復雜度： O(1)，原地排序演算法，

穩定性： 希爾排序法是不穩定的排序演算法，希爾排序演算法會將資料進行分組，對相距某一增量的一組資料進行插入排序，那么在排序的程序中因為是跳躍式的比較，也就很可能將相同元素的相對位置進行改變，

冒泡排序

基本思想

冒泡排序*(Bubble Sort)* 是一種交換排序演算法，基本思想為：對一組有 n 個元素的資料，每次比較相鄰兩個元素的大小，如果是逆序排列，則交換兩個元素的位置，直到所有元素有序為止，

代碼實作

以上圖為例，對 [5, 3, 7, 1, 2, 6, 4, 8]這組資料進行排序 ，首先比較 5 和 3 的大小，5 > 3 因此交換 5 和 3 的位置，得到[3, 5, 7, 1, 2, 6, 4, 8]

接著再比較 5 和 7 的大小，5 <= 7 則不交換，

繼續比較后面相鄰的兩個元素大小， 并按照相同的判斷來決定兩個元素是否交換，直到遍歷完未排序元素中最后兩個元素時，本輪比較完畢，

可以發現通過一輪比較可以將未排序元素中最大的元素放置在未排序元素的最后一個位置，并且這個元素所處的位置也是整個排序完畢之后應該處于的位置，

所以對于給出的這組資料，只需要進行 7 輪比較就能確定 7 個較大元素的最終位置，而最后一個元素也自然是處于其最終位置上 ，那么如果是一組有 n 個元素的資料，只需要進行 n - 1 輪比較就可以完成排序，并且，因為每一輪都確定了一個元素的最終位置，所以每進行下一輪比較時，上一輪確定位置的元素及其后面的所有元素都無需進行比較，假設進行第 i + 1 輪比較，之前就確定了 i 個元素的位置，本輪比較的最后兩個元素只需要到 n - i - 1 和 n - i 即可，最終 n - i 位置上也會在放置剩余元素中最大的一個元素，

代碼實作：

public class BubbleSort {
    
    public static <E extends Comparable<E>> void bubbleSort1(E[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) { 
            for (int j = 0; j < n - 1 - i; j++) {  
                if (array[j].compareTo(array[j + 1]) > 0) {
                    swap(array, j, j + 1);
                }
            }
        }
    }
    public static <E extends Comparable<E>> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

優化版1

對于一組已經基本有序的資料，在經過幾輪排序后，整組資料可能已經是完全有序的了，那么也就沒必要再對剩余的元素挨個進行比較，所以在每一輪比較開始時都假設陣列已經有序，如果在本輪比較中相鄰元素間并沒有進行交換，那么就可以證明假設是正確的，直接退出回圈即可，

具體操作上，在進入外層回圈后定義布爾變數 isSorted 初始化為 true，當在內層回圈中發生交換行為時，將其置為 false，內層回圈結束時，如果 isSorted == true，說明沒有發生交換行為，即陣列已經有序，則回圈終止，如果 isSorted == false，說明發生了交換行為，即陣列依然可能無序，繼續下次回圈，

public class BubbleSort {


    public static <E extends Comparable<E>> void bubbleSort(E[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            boolean isSorted = true;  // 本輪交換開始假設陣列已經有序
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j].compareTo(array[j + 1]) > 0) {
                    swap(array, j, j + 1);
                    isSorted = false;  // 執行交換操作，則陣列依然可能無序
                }
            }
            if (isSorted)  // isSorted == true, 則陣列已經有序
                break;
        }
    }
    public static <E extends Comparable<E>> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

優化版2

如果是一組前面無序，而后面有序的資料，對于后面有序區間內的比較是沒有必要的，但是根據上面版本的 Bubble Sort 除非陣列完全有序，否則依然會將后面已經有序的資料再次比較一遍，而對于有序區間內的比較不會產生交換操作，所以每一輪比較完畢后，最后一次交換操作發生的位置及其后面的所有元素都是有序的，因此，可以紀錄每輪比較的最后一次交換操作發生的位置，整組資料的元素總個數 - 最后一次交換的位置 = 有序元素的個數，對于內外兩層回圈的判斷都可以基于有序元素的個數，外層回圈根據有序元素的個數決定是否進入回圈，內層回圈根據有序元素的個數決定本輪比較的邊界位置，

public class BubbleSort {

    public static <E extends Comparable<E>> void bubbleSort(E[] array) {
        for (int i = 0; i < array.length - 1; ) {
            int last = 0;  // 紀錄本輪最后一次交換位置，初始為0
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j].compareTo(array[j + 1]) > 0) {
                    swap(array, j, j + 1);
                    last = j + 1;     // 紀錄交換位置，[j + 1, n) 之間為有序元素
                }
            }
            i = array.length - last;  // array.length - last，計算已經有序的元素個數，并賦值給 i
        }
    }
    
    public static <E extends Comparable<E>> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

復雜度分析

時間復雜度： O(n²)，冒泡排序在完全逆序的情況下，需要兩兩比較無序區間中的所有元素，總的比較次數同樣也是 1 + 2 + 3 + … + (n - 1) = n(n-1)/2 ，所以時間復雜度是 O(n²)，

空間復雜度： O(1) ，原地排序演算法，

穩定性： 冒泡排序法是穩定的排序演算法，冒泡排序法每一次都是比較相鄰兩個元素的大小關系，如果存在逆序關系則交換，所以不是逆序關系的兩個元素是不會進行位置的交換，也就保證了相同元素的相對位置不會發生改變，

堆排序

基本思想

堆排序(Heap sort)是借助了堆這種資料結構來完成排序的演算法，如果沒有了解過堆這種資料結構的同學可以參考這篇博客：堆和優先佇列，里面比較詳細的介紹了堆排序中所應用的幾個函式，

堆排序的基本思想是將待排序的陣列構建成一個大堆或小堆(根據需求而定)，然后根據堆的特性，交換堆頂元素和堆底最后一個元素(陣列最后一個元素)進行交換，那么此時陣列最后一個元素就是整個陣列中的最大值(以升序排列為例)，因為堆頂元素此時不滿足堆的性質，所以要對堆頂元素執行下沉(Sift Down)操作，在 Sift Down 的程序中不應該對已經有序的元素進行操作，也就是被交換至陣列末尾的元素此時已經不屬于這個堆中的元素了，因此在 Sift Down 的具體程序中需要使用一個變數，來控制 Sift Down 所能操作的范圍，當操作完畢后再將新的堆頂元素與陣列倒數第二個元素進行交換，以此類推直到整個陣列排序完畢，

代碼實作

public class HeapSort {

    /**
     * 原地堆排序
     * 核心思路：將待排序的陣列看成一個堆，使用heapify的方式構建成一個堆，當形成堆以后堆頂的元素為陣列中最大的元素，將
     * 這個元素與堆底(陣列最后一個)元素進行交換，那么此時陣列最大的元素就被放置在了它應該存在的位置，而因為堆頂的元素此
     * 刻不在是堆中最大的元素，應該再次siftDown()將該元素下沉重新形成堆，接著再將新的堆頂元素與新的堆底(陣列倒數第二)元
     * 素進行交換，那么此時陣列第二大的元素就被放置再了它應該存在的位置，...以此類推，直到堆中所有元素都被重新放置，
     *
     * 通過上面的分析，需要維護一個指標 end 初始指向陣列最后一個元素的位置，整個排序程序中所維持的回圈不變數為：
     * [end + 1, arr.len)區間為已經排序的元素，[0,end]區間具備大根堆的特性，并且區間內都是未排序的元素
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        System.out.println("****************原地堆排序****************");
        int end = arr.length - 1;
        heapify(arr);  // 將陣列轉換為堆
        while (end > 0) {
            swap(arr, 0, end);
            siftDown(arr, 0, end);  // 維持[0, end]區間內大根堆的特性，
            end--;    // 維持[end + 1, arr.len) 區間為已經排序的元素
        }
    }


    /**
     * 將傳入的陣列構建為最大堆
     * 核心思路：從最后一個非葉子節點開始siftDown，直到根節點siftDown完畢，
     */
    private static <E extends Comparable<E>> void heapify(E[] arr) {
        if (arr == null)
            throw new NullPointerException();
        if (arr.length <= 1)
            return;

        /**
         * 求最后一個非葉子節點的下標:
         * 1. 最后一個葉子節點下標 = arr.length - 1
         * 2. 父節點的下標 =  (子節點下標 - 1) / 2
         * 3. 最后一個葉子節點的父節點即為最后一個非葉子節點，因此公式為:
         *    lastNonLeaf = (arr.length - 2) / 2
         */
        int nonLeaf = (arr.length - 1 - 1) / 2;
        while (nonLeaf >= 0) {
            siftDown(arr, nonLeaf, arr.length);
            nonLeaf--;
        }
    }


    /**
     * 將所維護的最大堆 heap 在索引 p 位置上的元素進行下沉
     *
     */
    private static <E extends Comparable<E>> void siftDown(E[] heap, int p, int size) {
        E parent = heap[p];
        int half = size >>> 1;
        while (p < half) {
            int c = (p << 1) + 1;
            if (c + 1 < size &&
                    heap[c + 1].compareTo(heap[c]) > 0)
                c++;
            if (parent.compareTo(heap[c]) > 0)
                break;
            heap[p] = heap[c];
            p = c;
        }
        heap[p] = parent;
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}

復雜度分析

時間復雜度： O(nlogn)，堆排序主要進行兩個操作，首先是 heapify 將陣列整理成堆的形式，這個程序的時間復雜度為 O(n)，其次是要進行 n - 1 次的 Sift Down 操作對陣列進行排序，每一次 Sift Down 最差時間復雜度為 O(logn)，因此堆排序總的時間復雜度為 O(nlogn)，

空間復雜度： O(1)，這一版的堆排序使用的原地排序版本，

穩定性： 堆排序法是不穩定的排序演算法，堆的底層資料組織結構是一顆完全二叉樹，底層容器是陣列，那么在排序程序中每次將堆頂元素與未排序的最后一個元素進行交換，接著被交換至堆頂的元素會進行 siftdown 操作，交換程序是跳躍式的，而 siftdown 的操作也可能改變兩個相同元素間的相對位置，

歸并排序

基本思想

歸并排序(Merge Sort)的基本思想是將一個陣列一分為二劃分為更小的兩個子陣列，如果能對這兩個子陣列進行排序，并在排序后將兩個子陣列進行合并，那么整個陣列的排序問題就能得到解決，而如何解決子陣列的排序問題？同理，繼續將兩個子陣列一分為二為 4 個子陣列，8 個子陣列… 直到子陣列長度為 1 時不可劃分，那么此時每一個長度為 1 的子陣列都是有序的，再將與其相鄰的子陣列進行合并為更大的有序陣列，那么經過不斷的合并，最終就能將整個陣列合并成完成有序的形式，

代碼實作

具體實作上，從上述的描述中不難發現，使用遞回的方式來實作歸并排序演算法要容易許多，如果學習過二叉樹的話對于遞回部分的代碼實作應該不難，

1. 首先考慮遞回函式的引數，如果要將陣列一分為二，那么就需要使用陣列的左右下標來進行計算，因此遞回函式的引數必須要有待排序陣列，陣列的左右下標
2. 其次需要定義遞回的終止條件，當遞回函式所包含的子陣列中只存在一個區間時，也就沒有子陣列可以再一分為二，所以此時應該終止遞回，
3. 最后再來考慮如何將陣列一分為二，需要通過左右下標來計算陣列的中間值，并以中間值來劃分左右子陣列的區間，

遞回函式代碼：

public class MergeSort {
    // 對外的公共介面
	public static <E extends Comparable<E>> void sort(E[] arr) {
        // 呼叫私有的方法, 將待排序陣列，以及陣列的左右邊界下標傳入
        mergeSort(arr, 0, arr.length - 1);
    }

    // 遞回函式的實作
    // arr 待排序的陣列
    // l 當前陣列的左邊界
    // r 當前陣列的右邊界
    private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r) {

        if (l >= r)  // 當陣列只有一個元素時終止遞回
            return;
        // 計算出中間值，并以中間值將陣列拆分成兩半
        // int mid = (l + r) / 2;   l + r 可能會整型溢位，因此采用下面的計算方式
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        // 拆分完畢后，再將陣列進行合并
        merge(arr, l, mid, r);
    }
}

在遞回函式最后有一個 merge 函式，它表示當拆分完畢后就需要對兩個子陣列進行合并的操作，而這個 merge 算是整個歸并排序演算法的核心部分，函式的引數中傳遞了待排序的陣列，和 l, mid, r 三個邊界變數，在這一版的 merge 函式中，是對 [l…mid] 和 *[mid + 1…r]*這兩個子陣列進行合并，也可以理解為是對這個兩個區間進行排序，在具體實作上，需要申請一塊大小為 r - l +1 的空間作為新陣列，并將原陣列 [l…r] 區間的元素拷貝至新陣列中，同時定義兩個指標分別指向新陣列中相應的兩個子陣列的起始位置，并比較兩個子陣列上元素的大小，將較小(或較大)的元素放入原陣列的相應位置上,一直到原陣列的 [l…r] 被重新有序的覆寫，

merge 的代碼：

 /**
     * 合并兩個有序區間 [l...mid] 和 [mid + 1...r]
     * 將陣列 arr [l...r] 區間的內容拷貝至陣列 temp 中，新拷貝的 temp 陣列起始位置從 0 開始，
     * 1. 定義指標 i 初始指向 l, 即左子陣列的左邊界位置，指標 i 掃描 temp 陣列中的左子陣列, 因為 temp 陣列起始位置從 0
     * 開始, 因此在具體指向時要考慮偏移量的問題, 偏移量為 l，
     * 2. 定義指標 j 初始指向 mid + 1, 即右子陣列的左邊界位置，指標 j 掃描 temp 陣列中的右子陣列, 同樣需要考慮偏移量的
     * 問題, 偏移量為 l
     * 3. 定義指標 k 初始指向 l, 指標 k 用于從[l...r]掃描陣列 arr, 每一次掃描都將放置一個較小或較大的元素在 arr[k] 位
     * 置上, 一直到 k > r, 表示陣列 arr[l...r] 區間以及被有序重新覆寫，
     * 
     * 在回圈中比較 temp[i-l] 和 temp[j-l] 的大小, 將較小(或較大)的元素放入到 arr[k] 位置上, 同時將指向較小(或較大)元
     * 素的指標 i 或 j 進行右偏移( +1 )，因為 i 掃描為左子陣列, 左子陣列的左右邊界為 [l,mid], 所以當 i > mid 時, 表示
     * 整個左子陣列都掃描完畢, 如果 k 還未到達 r 的位置, 那么就將右子陣列中的剩余元素依次放入到 [k...r] 區間中，同理 j 
     * 掃描為右子陣列, 右子陣列中的左右邊界為 [mid + 1, r], 所以當 j > r 時, 表示整個右子陣列都掃描完畢, 則將左子陣列剩
     * 余元素依次放入到 [k...r] 區間中，知道 k > r 時退出回圈, 歸并完畢，
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {

        // 歸并排序不是原地排序演算法，需要額外開辟 r - l + 1 大小的空間
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);

        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {  
                arr[k] = temp[j - l];  
                j++;
            } else if (j > r) {    
                arr[k] = temp[i - l];
                i++;
            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {  // <= 保證排序穩定性
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
            }
        }
    }

上述兩段代碼就是歸并排序的完整實作，排序的執行流程如下圖：

優化版

上一版的歸并排序演算法，還有一些地方可以進行優化，優化點如下：

1. 如果待合并的兩個陣列已經為有序情況，這里默認為從小到大的升序，也就是左子陣列中的最大值（上述代碼中 arr[mid] 位置的元素）如果已經小于等于右子陣列中的最小值（*arr[mid + 1]*位置的元素）那么就說明左子陣列中所有元素都小于等于右子陣列中的所有元素，這種情況下其實就沒必要再進行歸并，所以具體在呼叫 merge 函式時可以進行判斷，如果 arr[mid] > arr[mid + 1] 時才選擇呼叫 merge 函式，
2. 對 merge 函式的每一次呼叫都需要將重新開辟一塊記憶體空間，而每一次向記憶體申請空間都會占有一定開銷，如果資料規模過大時可能會造成性能的損耗，解決的方法是在公共介面 sort 函式中，先將申請一個大小為 arr 長度的陣列 temp 并將 temp 作為引數傳遞至 merge 函式中，這樣在每次 merge 前只需要將 arr [l…r] 位置的元素拷貝至 temp[l…r] 位置上即可，而且因為 arr 和 temp 是大小相同的陣列，所以在合并程序中也無序在考慮偏移量的問題，

完整代碼：

public class MergeSort {
	public static <E extends Comparable<E>> void sort(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);  // 優化位置 
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r, E[] temp) {

        if (l >= r)
            return;

        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid, temp);
        mergeSort(arr, mid + 1, r, temp);
        if (arr[mid].compareTo(arr[mid + 1]) > 0) // 優化位置
            merge(arr, l, mid, r, temp);  
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int m, int r, E[] temp) {

        System.arraycopy(arr, l, temp, l, r - l + 1);  // 將arr[l...r]的內容 拷貝至 temp[l...r]

        // 因為temp陣列與arr陣列大小相同，元素所處的位置也相同，因此不必在考慮偏移量的位置
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) {
            if (i > m) {
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }
    }
}

自底向上版

自底向上的歸并排序是一種非遞回的實作方式，其基本思想是從最底層出發不斷向上解決問題，最初從最小的陣列開始執行 merge 操作，將只有 1 個元素的 2 個子陣列歸并成 1 個包含 2 個元素的有序子陣列，接著再對有 2 個元素的有序子陣列歸并成含有 4 個元素的有序子陣列，重復操作直到將整個陣列歸并，

自底向上是相對于遞回樹而言，從遞回實作的角度來看是從頂層(整個陣列)出發，將整個陣列不斷拆分成小的陣列，直到拆分為原子陣列時，在對兩兩相鄰的子陣列進行合并，拆分的程序是發生在向下遞回的程序中，而合并的操作是發生在向上回傳的程序，其實個人覺得，自底向上的操作方式其實與遞回程序中向上回傳的操作很相似，

代碼實作：

public class MergeSort {
	public static <E extends Comparable<E>> void sortBU(E[] arr) {
        int n = arr.length;
        E[] temp = Arrays.copyOf(arr, arr.length);
        /**
         * 對兩個大小為 sz 的有序陣列進行歸并操作
         * sz 初始等于 1, 表示第一輪回圈時, 將對大小為 1 的兩個有序陣列進行歸并, 既是對[0,1]、[1,2]、[2,3]...
         * [n-2,n-1] 區間進行排序, 當內層回圈退出時, 有序陣列的大小為之前的兩倍, 所以外層回圈控制回圈變數 sz 為兩倍增
         * 長，表示再次進入回圈時，對上一輪歸并后長度為 sz 的兩個子陣列再次進行合并，直到 sz == n 時，表示整個 arr 數
         * 組排序完畢，
         *
         * 變數解釋:
         *  1. sz, 歸并兩個子陣列的大小
         *
         *  2. l, 靠左子陣列的左邊界, 初始為0，
         *  -- 當每次歸并完兩個子陣列后, l 應該移動到下一對子陣列的左邊界位置, 即 l += sz + sz，
         *  -- l + sz < n; 時, 表示還存在兩個子陣列可以進行歸并，
         *
         *  3. mid, 靠左子陣列的右邊界, 即 [l,mid] 為左子陣列，
         *  -- mid = l + sz - 1; 左子陣列大小為 sz, 所以 l + sz - 1 表示為左子陣列的右邊界
         *
         *  4. r, 靠右子陣列的右邊界，mid 為左子陣列的右邊界, 而兩個子陣列是緊挨著的, 所以 mid + 1 為右子陣列的左邊界
         *  即 [mid + 1, r] 為右子陣列，
         *  -- r = Math.min((mid + sz), (n - 1)); mid + sz, 即可以取到右子陣列的右邊界, 但是當陣列 arr 的長度并
         *  不是 2 的整數次冪時, 無法對整個陣列進行平均拆分, 最后一個子陣列一定是少于 sz 的, 所以不能直接讓 
         *  r = mid +  sz, 這樣會導致在歸并最后兩個陣列時, 出現下標越界, 正確的做法是取 mid + sz 和 n - 1的較小值, 
         *  n - 1 即為 arr 陣列最后一元素的下標，
         */
		for (int sz = 1; sz < n; sz += sz) {
            for (int l = 0; l + sz < n; l += sz + sz) {
                int mid = l + sz - 1;
                int r = Math.min((mid + sz), (n - 1));
                if (arr[mid].compareTo(arr[l + sz]) > 0) {
                    mergeBU(arr, l, mid, r,temp);
                }
            }
        }

    private static <E extends Comparable<E>> void mergeBU(E[] arr, int l, int m, int r, E[] temp) {
        System.arraycopy(arr, l, temp, l, r - l + 1);

        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) {
            if (i > m) {
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }
    }
}

復雜度分析

時間復雜度：O(nlogn)，歸并排序演算法每一層的遞回呼叫都對兩兩相鄰的子陣列進行歸并操作，歸并操作會將兩個子陣列的區間掃描一遍，所以每一層都對整個陣列進行了一遍掃描，一層的操作總數為 n，而遞回樹的總深度為 logn + 1 層，所以總的時間復雜度為 O(nlogn)，

最好情況下，也就是陣列完全有序的情況下，基于上面的優化并不會進入 merge 函式中進行歸并，那么每一個遞回函式中的運算元都是 O(1) 級別，將遞回函式看作遞回樹中的一個節點，那么遞回樹中有多少個節點，就進行了多少次的 O(1) 操作，歸并排序的遞回樹是一顆滿二叉樹，最底層的葉子節點數量為陣列元素個數 n ，上一層節點個數為 n/2，在上一層為 n/4 … 一直到根節點時節點個數為 1，總的節點個數為 n + n / 2 + n / 4 + … + 1 ≈ 2n ，所以在陣列完全有序的情況下，歸并排序的時間復雜度為 O(n)，

空間復雜度：O(n)，因為歸并排序演算法不是原地排序演算法，需要額外申請一塊等同于待排序陣列大小的空間進行輔助排序，所以空間復雜度為 O(n)，

穩定性：規并排序法是穩定的排序演算法，對于歸并排序演算法來說，元素的移動發生在 merge 中，在歸并時沒有發生跳躍式的交換，并且如果兩個待合并的子陣列中存在相同的元素時，只需要保證前一個子陣列的相同元素先放入原陣列的對應位置，就可以保證整個排序演算法的穩定性，

快速排序

基本思想

快速排序(Quick Sort)演算法，被譽為20世紀十大演算法之一，其基本思想是對于一組待排序的資料，每一輪排序從待排序元素中選取一個標定點(pivot)，在排序的程序中使得 pivot 左側的元素小于或等于(默認升序排列) pivot，右側的元素大于或等于 pivot ，并以 pivot 為軸原陣列分割為較小的兩個子陣列，并對兩個子陣列分別進行如上操作，直到子陣列區間長度為 1 時，整個排序完畢，

快速排序的實作方式有很多種，比如：單路快速排序，雙路快速排序，三路快速排序等，由于篇幅有限這里主要介紹應用最多的雙路快速排序，對于單路快排而言當待排序陣列中出現大量重復元素時，快速排序會退化成 O(n²) 的排序演算法，了解即可，而對于三路快速排序而言，陣列中完全是重復元素時，時間復雜度可以達到 O(n) 級別，不過一般而言還是雙路快速排序演算法的性能更優，

代碼實作

具體實作上，首先需要了解如何選取 pivot ，以及如何使得 pivot 左側的元素都是小于等于 pivot，右側的元素都是大于等于 pivot，這其實是快速排序演算法中最為重要的一個操作，被定義在一個叫 partition 函式中，

partition(arr, l, r) 函式是對陣列的 [l…r] 區間進行排序，在 partition 的程序中會隨機選取一個 pivot (這里使用的是隨機選取法)， 并將 pivot 移動到 arr[l] (左邊界)的位置上，

接著定義兩個指標 i 初始指向 l + 1 位置，j 初始指向 r 位置，使用指標 i, j 從陣列左右兩端向中間遍歷，遍歷的程序中指標 i 需要維護 [l + 1… i - 1] 都是 <= pivot 的元素，而指標 j 需要維護 [j + 1…r] 都是 >= pivot 的元素，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-GpDE8ng6-1634830346729)(D:\課件\筆記\資料結構與演算法\七大排序演算法\image-20211021111001863.png)]

具體來說，當 arr[i] < pivot 時，i 向右移動(i++)，那么 [l + 1…i - 1] 區間的性質就被維護住，而當 arr[j] > pivot 時，j 向左移動(j–)，那么 *[j + 1…r]*區間的性質也被維護住，當 arr[i] >= pivot 并且 arr[j] <= pivot 時， arr[i] 和 arr[j] 指向的元素不滿足各自所需要為何區間的性質，因此交換 arr[i] 和 arr[j] ，使得兩個指標所維護的區間各自滿足區間的性質，重復操作直到 i >= j 時，整個陣列遍歷完畢，

當退出回圈后，arr[l + 1…i - 1] 的元素 <= pivot，arr[j + 1…r] 的元素 >= pivot，此時 j 指向了左區間 <= pivot 的最后一個元素，那么 j 指向的位置就是 pivot 應該處于的位置，交換 arr[l] 和 arr[j]，

j 此時指向 pivot ，那么就可以將 j 作為軸將陣列分割為兩個子區間 [l…j - 1] 和 [j + 1…r]，并分別對兩個子區間再執行上述操作，直到子區間中只存在一個元素時，就沒法繼續在拆分了，那么此時的整個陣列的排序也就完成了，通過觀察其實不難發現，對陣列的分割操作與歸并排序對陣列的一分為二操作很像，只是在快速排序中陣列的分割是以 pivot 為軸進行的，所以分割操作這一步其實也可以使用遞回實作，并且使用遞回實作也更加簡單，所以分割操作無需定義 partition 中，只需要接收 partition 函式回傳的 pivot 下標值即可，也就是j 的值，

代碼實作：

public class QuickSort {
    
   /**
    * 提供給外接的公共介面
    */
    public static <T extends Comparable<T>> void sort(T[] arr) {
        // 對[0, lengnth - 1]區間進行排序, 傳入一個Random物件用于partition函式中隨機生成 pivot
        quickSort(arr, 0, arr.length - 1, new Random());  
    }
	
   /**
    * 對陣列的分割操作, 基于 partition 函式回傳 pivot 的位置
    */
    private static <T extends Comparable<T>> void quickSort(T[] arr, int l, int r, Random rd) {
        // 區間只有一個元素時終止遞回
        if (l >= r) return; 
        
        int p = partition(arr, l, r, rd);
        quickSort(arr, l, p - 1, rd);
        quickSort(arr, p + 1, r, rd);
    }

   /**
	* 對[l...r]區間進行 parition 操作
	*/
    private static <T extends Comparable<T>> int partition(T[] arr, int l, int r, Random rd) {
        int p = rd.nextInt(r - l + 1) + l; // 生成[l,r]間的隨機索引，索引上的值作為 pivot
        swap(arr, l, p); // 將 pivot 移動到arr[l]的位置上
        // arr[l + 1...i - 1] <= arr[l] (pivot)
        // arr[j + 1...r] >= arr[l] (pivot)
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i].compareTo(arr[l]) < 0)
                i++;
            while (i <= j && arr[j].compareTo(arr[l]) > 0)
                j--;
            if (i >= j) break;
            swap(arr, i++, j--);
        }
        swap(arr, l, j);
        return j;
    }
    
    private static <T> void swap(T[] array, int left, int right) {
        T tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}

以上代碼實作實際上是經過優化后的代碼，大家可能存在一些疑惑，下面解釋一些自己在學習中遇到的疑問：

1. 為什么使用 Random 物件來隨機生成標定點？

   其主要解決的問題是如果陣列已經是有序的情況下，每次都直接選取 arr[l] 作為 pivot 那么每一輪的 partition 中，pivot 右邊的元素都是大于(默認升序) pivot 的，最終只能分割出一個區間，即為 [p + 1, r]，也就是每次只處理了一個元素，下一輪還需要處理 n - 1 個元素，n - 2，n - 3 … 1，這樣實際上總共 partition 了 n 輪，那么總共的執行次數就是 n + n - 1 + n - 2 + n - 3 + … + 1 = n( 1 + n )/2，時間復雜度就退化為 O(n²)，這個時間復雜度對于排序演算法來說就是非常慢的了，并且因為這一版的快速排序是遞回實作，那么當資料規模稍大時，遞回 n 層也很容易導致堆疊溢位的情況，

   而如果使用隨機生成標定點的方式，那么每次都選取到待排序區間中最小元素的概率就是 1/n, 1/n-1, 1/n-2, 1/n-3, … 1，總的概率就是每一次的概率相乘 = 1/n! ，這是非常低的概率，因為階乘的增長速度非常之快，當資料規模為 10 的時候，每一次 partition 選取最小值作為標定點的概率就為 1/ 3628800，如果碰上這種情況還需要敲什么代碼，直接買彩票就可以了，并且就算是在資料規模為 10 時遇上了這種情況，O(n²) 級別的演算法也能夠輕松應對，

   此外，解決有序陣列退化為 O(n²) 的方法還有幾數取中法，常見為三數取中，也就是分別取待排序區間的最左邊 l, 中間 m, 和最右邊 r，并對這三個位置上的值進行比較，最終形成 m <= l <= r 的排列，那么次數最左邊 l 上的值就是三個數中的中間值，這樣也可能很好的避免演算法效率退化的問題，

2. 為什么 i 維護的區間為 [l + 1…i - 1] <= pivot，j 維護的區間為 arr[j + 1…r] >= pivot ，但是當 arr[l] == pivot 或 arr[j] == pivot 時卻要停止 i 和 j 的移動呢？

   這是因為，當 arr 陣列中出現大量重復元素時，如果 i 和 j 遍歷到與 pivot 相同元素時不停止，而是繼續向中間移動，那么很容易使得 pivot 最終所處于的位置是非常偏向一邊的，甚至可能是最終 pivot 的一端一個元素都沒有(完全重復的情況)，那么如果每一次 partition 都出現這種情況，快速排序演算法依然會退化成一個 O(n²) 級別的演算法，所以上面設定的條件為當 arr[i] < pivot 和 arr[j] > pivot 時 i j 指標才繼續移動，而如果遇到等于的情況就會將相同的元素交換到另一端，并且兩個指標會繼續向中間位置移動，這樣就能盡可能的保證在資料有大量重復元素時 pivot 最終的位置也是處于靠中間的位置，

復雜度分析

時間復雜度： O(nlogn)，通常來說普通演算法的時間復雜度都是取最壞時間復雜度，快速排序的最壞時間復雜度為O(n²)，不過在上面實作的快速排序演算法屬于隨機演算法，出現最壞情況的概率非常之低，也就是沒有辦法*100%*的找到一組資料使得隨機快速排序退化為 O(n²) 級別的演算法，所以對于隨機演算法的時間復雜度不能簡單的取最壞時間復雜度，而是應該取復雜度的期望值，簡單理解就是從平均來看快速排序的時間復雜度，依然是 O(nlogn) 級別的演算法，（具體如何推導超出了博主的能力范疇，感興趣的同學可以參考《演算法導論》），

空間復雜度： O(1)，快速排序演算法屬于原地排序，不需要額外開辟更多的記憶體空間輔助排序，

穩定性：快速排序法是不穩定的排序演算法，在 partition 中程序中元素的交換是跳躍性的，并且每次隨機選擇一個元素作為標定點時，如果存在相同的元素那么它們的相對位置就會發生改變，

非遞回實作(代碼)

非遞回實作快速排序，使用了堆疊這種資料結構，將每次需要進行 partition 操作區間的左右邊界依次壓入堆疊中，再以相反的順序出堆疊進行下一次 parititon 操作，因為時間原因這里只貼出代碼供大家參考

public class QuickSort { 
    
    public static <T extends Comparable<T>> void sortByStack(T[] arr) {

        Random rnd = new Random();

        Stack<Integer> stack = new Stack<>();
        stack.push(0);  // 左邊界先入堆疊
        stack.push(arr.length - 1);  // 右邊界后入堆疊

        while (!stack.empty()) {
            int r = stack.pop();   // 右邊界先出堆疊
            int l = stack.pop();   // 左邊界后出堆疊
            int p = partition(arr, l, r, rnd);
            if (p + 1 < r) {   // pivot 右邊還存在兩個以上元素時 
                stack.push(p + 1);
                stack.push(r);
            }
            if (p - 1 > l) {  // pivot 左邊還存在兩個以上元素時
                stack.push(l);
                stack.push(p - 1);
            }
        }
    }
    
    private static <T extends Comparable<T>> int partition(T[] arr, int l, int r, Random rd) {
        int p = rd.nextInt(r - l + 1) + l;
        swap(arr, l, p);
        // arr[l + 1, i - 1] <= arr[l]
        // arr[j + 1, r] >= arr[l]
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i].compareTo(arr[l]) < 0)
                i++;
            while (i <= j && arr[j].compareTo(arr[l]) > 0)
                j--;
            if (i >= j) break;
            swap(arr, i++, j--);
        }
        swap(arr, l, j);
        return j;
    }
    
    private static <T> void swap(T[] array, int left, int right) {
        T tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}

三路快速排序(代碼)

三路快速排序，在處理陣列中存在大量重復資料時，效率很高，對于完全重復的資料時間復雜度可以達到 O(n) 級別，因為時間原因貼出之前畫的圖和代碼供大家參考，

代碼實作：

    // 三路快速排序
    public static <T extends Comparable<T>> void sort3Ways(T[] arr) {
        quickSort3Ways(arr, 0, arr.length - 1, new Random());
    }

    public static <T extends Comparable<T>> void quickSort3Ways(T[] arr, int left, int right, Random rd) {
        if (left >= right) return;
        Pair<Integer, Integer> border = partition3Ways(arr, left, right, rd);
        quickSort3Ways(arr, left, border.getKey(), rd);
        quickSort3Ways(arr, border.getValue(), right, rd);
    }


    private static <T extends Comparable<T>> Pair<Integer, Integer> partition3Ways(T[] arr, int left, int right, Random rd) {
        int p = rd.nextInt(right - left + 1) + left;
        swap(arr, left, p);
        // [left + 1, lt] < key   [lt + 1, i - 1] == key  [gt, right] > key
        int lt = left, i = left + 1, gt = right + 1;   
        while (i < gt) {
            if (arr[i].compareTo(arr[left]) < 0)
                swap(arr, ++lt, i++);  // lt + 1的元素 與 i的元素交換，并且lt 和 i 向后移動
            else if (arr[i].compareTo(arr[left]) > 0)
                swap(arr, --gt, i);   // gt - 1的元素 與 i的元素交換，并且 gt 向前移動，i 不變
            else  // arr[i] == arr[left]
                i++;
        }
        swap(arr, left, lt);
        // 交換完畢后：[left, lt - 1] < key   [lt, gt - 1] == key  [gt, right] > key
        return new Pair<>(lt - 1, gt);  
    }

    // 交換
    private static <T> void swap(T[] array, int left, int right) {
        T tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }