1 初級排序算法

排序算法關注的主要是重新排列數(shù)組元素，其中每個元素都有一個主鍵斜纪。排序算法是將所有元素主鍵按某種方式排列（通常是按照大小或是字母順序）矾端。排序后索引較大的主鍵大于等于索引較小的主鍵洞就。

排序算法類的模板

public class Example{
    public static void sort(Comparable a[]){}
    private static boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){
        for(int i = 0;  i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static boolean isSort(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        //從標準輸入讀入字符串，排序后輸出
        Integer[] a = new Integer[]{1,34,55,66,7};
        sort(a);
        assert isSort(a);
        show(a);
    }
}

• 排序成本模型：研究排序算法時肾胯，需要計算比較和交換的次數(shù)竖席。對于不交換元素的算法耘纱，計算訪問數(shù)組的次數(shù)。
• 額外內(nèi)存使用：排序算法的額外內(nèi)存開銷和運行時間同等重要毕荐。排序算法可分兩類：除了函數(shù)調(diào)用所需的棧和固定數(shù)目的實例變量之外無需額外內(nèi)存的原地排序算法束析，以及需要額外內(nèi)存空間來存儲另一份數(shù)組副本的其它排序算法。
• 數(shù)據(jù)類型：上述排序算法模板適用于任何實現(xiàn)了Comparable接口的數(shù)據(jù)類型憎亚。例如员寇，Java中封裝的Integer和Double，以及String和其他許多高級數(shù)據(jù)類型（如File和URL）都實現(xiàn)了Comparable接口第美，因此可以直接調(diào)用這些類型的數(shù)組作為參數(shù)調(diào)用我們自己實現(xiàn)的排序方法蝶锋。

例如——用快排對N個隨機的Double數(shù)據(jù)進行排序：

Doulbe[] a = new Double[N];
for(int i = 0; i < N; i++){
    a[i] = StdRandom.uniform();
    Quick.sort(a);
}

在創(chuàng)建自己的數(shù)據(jù)類型時，只要實現(xiàn)Comparable接口并實現(xiàn)該接口中的compareTo()方法什往，來定義目標類型對象的自然次序扳缕，如：

public class MyDate implements Comparable<MyDate>{
    private final int day;
    private final int month;
    private final int year;
    public MyDate(int d, int m, int y){
        day = d;
        month = m;
        year = y;
    }
    public int compareTo(MyDate that){
        if(year > that.year) return +1;
        if(year < that.year) return -1;
        if(month > that.month) return +1;
        if(month < that.month) return -1;
        if(day > that.day) return +1;
        if(day < that.day) return -1;
        return 0;
    }
}

對于 v < w、v = w 和 v > w 三種情況别威，Java習慣是在v.compareTo(w)被調(diào)用時分別返回一個負整數(shù)躯舔、零和一個正整數(shù)（-1、0和1）省古。一般來說庸毫，若 v 和 w 無法比較或者兩者之一是 null，v.compareTo(w) 將會拋出一個異常衫樊。

1.1 選擇排序

選擇排序：首先找到數(shù)組中最小的元素飒赃，其次，將它和數(shù)組的第一個元素交換位置（如果第一個元素最小就和自己交換）科侈。再次载佳，在剩下元素中找到最小的元素，將它與數(shù)組的第二個元素交換位置臀栈。如此往復蔫慧，直到將整個數(shù)組排序。這種方法叫做選擇排序权薯，因為它在不斷選擇剩余元素中的最小者姑躲。

less()、exch()和isSort()的實現(xiàn)見排序算法類的模板

public class Selection {
    public static void sort(Comparable[] a) {
        //將a[]按升序排列
        int N = a.length;
        for (int i = 0; i < N; i++) {
            //將a[i] 和 a[i+1...N]中的最小元素交換
            int min = i;//最小元素索引
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            exch(a, i, min);
        }
    }
    public static void main(String[] args) {
        //從標準輸入讀入字符串盟蚣，排序后輸出
        Integer[] a = new Integer[]{1,354,55,66,7};
        sort(a);
        assert isSort(a):"Error Information...";
        show(a);
    }
}

選擇排序內(nèi)循環(huán)只是在比較當前元素與目前已知最小元素（以及將當前索引加1和檢查是否代碼越界）黍析，交換元素的代碼寫到了內(nèi)循環(huán)之外，每次交換都能排定一個元素屎开，因此交換總次數(shù)是N阐枣。所以算法總的時間效率取決于比較次數(shù)。

• 長度為 N 的數(shù)組沮焕，選擇排序需要大約 (N^2) / 2 次比較和 N 次交換

0 到 N-1 的任意 i 都會進行一次交換和 N-1-i 次比較除秀，因此總共有 N 次交換以及(N-1)+(N-2)+...+2+1 = N(N-1) / 2 ~ N^2 / 2次比較

• 選擇排序有兩個鮮明特點：

1. 運行時間和輸入無關。為了找出最小元素而掃描一遍數(shù)組并不能為下一遍掃描提供什么信息供炎。這種情況在某些情況下是缺點额划，因為一個已經(jīng)有序的數(shù)組或是主鍵全部相等的數(shù)組和一個元素隨機排列的數(shù)組所用的排序時間一樣長妙啃，而其它算法更善于利用輸入的初始狀態(tài)。
2. 數(shù)據(jù)移動最少俊戳。每次交換都會改變兩個數(shù)組元素的值揖赴，因此選擇排序用了N次交換——交換次數(shù)和數(shù)組大小是線性關系，而其它任何算法都不具備這個特征（大部分增長數(shù)量級都是線性對數(shù)或平方級別）品抽。

1.2 插入排序

插入排序：整理撲克時一般都是一張一張來储笑，將每張牌插入到其它已經(jīng)有序的牌中的適當位置。在計算機實現(xiàn)中圆恤，為了要給插入元素騰出空間突倍，需要將其余所有元素在插入之前都向右移動一位。這種算法叫做插入排序盆昙。

• 與選擇排序一樣羽历，當前索引左邊所有元素都是有序的，但它們最終位置還不確定淡喜，為了給更小元素騰出空間秕磷，它們可能會被移動，但當索引到達數(shù)組右端時炼团，數(shù)組排序就完成了澎嚣。
• 與選擇排序不同的是，插入排序所需時間取決于輸入中元素的初始順序瘟芝。如對接近有序的數(shù)組排序要比隨機數(shù)組快很多易桃。

對于隨機排列的長度為N且主鍵不重復的數(shù)組，平均情況下插入排序需要 ~ N^2 / 4$ 次比較以及~N^2 / 4 次交換锌俱。最壞情況下需要 ~ N^2 / 2 次比較和 ~N^2 / 2 次交換晤郑，最好情況下需要 N-1 次比較和 0 次交換。

public class Insertion{
    //第1種實現(xiàn)
    public static void sort1(Comparable[] a){
        int N = a.length;
        for(int i = 1; i < N; i++){
            for(int j = i; j > 0 && less(a[j], a[j - 1]); j--){
                exch(a, j, j - 1);
            }
        }
    }
    // 第2種實現(xiàn)
    public static void sort2(Comparable[] a){
        int N = a.length, j;
        for(int i = 1; i < N; i++){
            Comparable key = a[i];
            j = i - 1;
            //注意 j >= 0
            while(j >= 0 && less(key, a[i])){
                a[j + 1] = a[j];
                j -= 1;
            }
            a[j + 1] = key;
        }
    }
}

考慮一般情況下部分有序的數(shù)組贸宏。倒置指的是數(shù)組中兩個順序顛倒的元素造寝。比如EXAMPLE中有11對倒置：E-A,X-A,X-M,X-P,X-L,X-E,M-L,M-E,P-L,P-E和L-E。若數(shù)組中倒置的數(shù)量小于數(shù)組大小的某個倍數(shù)吭练，則這個數(shù)組是部分有序诫龙。插入排序?qū)@樣的數(shù)組很有效，事實上线脚，當?shù)怪脭?shù)量很小時赐稽，插入排序可能比其它任何算法都快叫榕。

插入排序的交換操作和數(shù)組中倒置數(shù)量相同浑侥，需要比較的次數(shù)大于等于倒置的數(shù)量姊舵，小于等于倒置的數(shù)量加上數(shù)組的大小再減一。要大幅提高插入排序速度并不難寓落，只需在內(nèi)循環(huán)中將較大元素都向右移而不總是交換兩個元素（這樣訪問數(shù)組次數(shù)就能減半）括丁，即上述第2種實現(xiàn)。

1.3 希爾排序

希爾排序：是一種基于插入排序的排序算法伶选。對于大規(guī)模亂序數(shù)組插入排序很慢史飞，因為它只會交換相鄰的元素，若最小元素在數(shù)組末尾仰税，則對其需要移動N-1次构资。希爾排序改進了插入排序，交換不相鄰的元素以對數(shù)組的局部進行排序陨簇，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序吐绵。

• h有序數(shù)組：數(shù)組中任意間隔為 h 的元素都有序。即一個 h有序數(shù)組 就是 h 個互相獨立的有序數(shù)組編織在一起組成的一個數(shù)組河绽。若h很大己单，則可將元素移到很遠位置，為實現(xiàn)更小的h有序創(chuàng)造方便耙饰。

public class Shell{
    //第1種實現(xiàn)
    public static void sort1(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                //注意 j >= h
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h /= 3;
        }
    }
    //less()纹笼、exch()和isSort()見排序算法類的模板

    //第2種實現(xiàn)
    public static void sort2(Comparable[] a) {
        int N = a.length;
        //初始化gap，逐步縮小gap苟跪，直到1
        for (int gap = N / 2; gap >= 1; gap /= 2) {
            //每組都從第gap個元素開始進行直接插入排序
            for (int i = gap; i < N; i++) {
                //插入排序
                Comparable key = a[i];
                int j = i - gap;
                //注意 j >= 0
                while (j >= 0 && less(key,a[j])){
                    a[j + gap] = a[j];
                    j -= gap;
                }
                a[j + gap] = key;
            }
        }
    }
}

算法實例解釋可參考：
白話經(jīng)典算法系列之三 希爾排序的實現(xiàn)
圖解排序算法(二)之希爾排序

希爾排序更高效原因是它權衡了子數(shù)組的規(guī)模和有序性廷痘。排序之初，各個子數(shù)組都很短件已，排序之后子數(shù)組都是部分有序的笋额，這兩種情況都適合插入排序。子數(shù)組部分有序的程度取決于遞增序列的選擇拨齐。

1.4 歸并排序

歸并排序：將一個數(shù)組排序鳞陨，可以先（遞歸地）將它分成兩半分別排序，然后將結(jié)果歸并起來瞻惋。歸并排序?qū)㈤L度為N的數(shù)組排序所需時間和 NlogN 成正比厦滤；所需額外空間和 N 成正比。

原地歸并的抽象方法——merge()

public static void merge(Comparable[] a, int lo, int mid, int hi){
    //將 a[lo...mid] 和 a[mid...hi] 歸并
    int i = lo, j = mid + 1;
    //將 a[lo...hi] 復制到 aux[lo...hi]
    for(int k = lo; k <= hi; k++){
        aux[k] = a[k];
    }
    //歸并回到 a[lo...aux]
    for(int k = lo; k <= hi; k++){
        if(i > mid){
            a[k] = aux[j++];
        }else if(j > hi){
            a[k] = aux[i++];
        }else if(less(aux[i], aux[j])){
            a[k] = a[i++];
        }else{
            a[k] = a[j++];
        }
    }
}

上述方法將所有元素復制到一個輔助數(shù)組aux[]中歼狼，再把歸并結(jié)果放回原數(shù)組a[]中掏导。方法在歸并時（第二個for循環(huán)）進行了4個判斷：左半邊用盡（取右半邊元素）、右半邊用盡（取左半邊元素）羽峰、左半邊的當前元素小于右半邊的當前元素（取左半邊元素）以及右半邊的當前元素小于左半邊的當前元素（取右半邊元素）

自頂向下的歸并排序

public class Merge extends Example {
    //歸并所需輔助數(shù)組
    private static Comparable[] aux;
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        //將a[]復制到aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        //注意：比較元素都用aux[]
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        //左半邊排序
        sort(a, lo, mid);
        //右半邊排序
        sort(a, mid + 1, hi);
        //歸并結(jié)果
        merge(a, lo, mid, hi);
    }
    public static void main(String[] args) {
        //從標準輸入讀入字符串趟咆，排序后輸出
        Integer[] a = new Integer[]{49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
        sort(a);
        assert isSort(a) : "Error Information...";
        show(a);
    }
}

1. 對于長度為 N 的數(shù)組添瓷，自頂向下的歸并排序需要 1/2NlogN 至 NlogN 次比較
2. 對于長度為 N 的數(shù)組，自頂向下的歸并排序最多需要訪問數(shù)組 6NlogN 次

歸并排序所需時間和 NlogN 成正比值纱，主要缺點是輔助數(shù)組所使用的額外空間和 N 的大小成正比鳞贷。

歸并改進：

• 對小規(guī)模數(shù)組使用插入排序。使用插入排序處理小規(guī)模的子數(shù)組虐唠，一般可以將歸并排序運行時間縮短10%~15%搀愧。
• 測試數(shù)組是否已經(jīng)有序。添加一個判斷條件疆偿，若 a[mid] <= a[mid + 1] 則認為數(shù)組已經(jīng)有序并跳過 merge() 方法咱筛。這個改動不影響排序的遞歸調(diào)用，但任意有序的子數(shù)組算法的運行時間就變?yōu)榫€性了杆故。
• 不將元素復制到輔助數(shù)組迅箩。可以節(jié)省元素復制到輔助數(shù)組所用時間（但空間不行）处铛，此時需調(diào)用兩種排序方法饲趋，一種從輸入數(shù)組排序到輔助數(shù)組，一種從輔助數(shù)組排序到輸入數(shù)組罢缸，技巧是在遞歸調(diào)用的每個層次交換輸入數(shù)組和輔助數(shù)組的角色篙贸。

自底向上的歸并排序

先歸并微型數(shù)組，然后再成對歸并得到的子數(shù)組枫疆，直到將整個數(shù)組歸并到一起爵川，這比標準遞歸方法所需代碼量少。首先是兩兩歸并（每個元素是大小為1的數(shù)組）息楔，然后四四歸并（將兩個大小為2的數(shù)組歸并成一個有4個元素的數(shù)組）寝贡，然后是八八歸并...

    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        //sz 子數(shù)組大小
        for (int sz = 1; sz < N; sz += sz) {
            //lo 子數(shù)組索引
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }

自底向上歸并排序會多次遍歷整個數(shù)組，根據(jù)子數(shù)組大小進行兩兩歸并值依，子數(shù)組大小sz初始值為1圃泡，每次加倍。最后一個子數(shù)組大小只有在數(shù)組大小是sz的偶數(shù)倍時才等于sz（否則會比sz性赶铡）颇蜡。

自底向上的歸并排序的歸并結(jié)果

長度為 N 的數(shù)組，自底向上的歸并排序需 1/2NlogN 至 NlogN 次比較辆亏，最多訪問數(shù)組 6NlogN 次风秤。

• 當數(shù)組長度為2的冪時，自頂向下和自底向上歸并排序所用比較和訪問次數(shù)相同扮叨，只是順序不同缤弦。
• 自底向上歸并排序適合用鏈表組織數(shù)據(jù)。此方法只需重新組織鏈表連接就能將鏈表原地排序（不需創(chuàng)建任何新的鏈表節(jié)點）彻磁。

用自頂向下或自底向上方式實現(xiàn)任何分治算法都很自然碍沐。歸并排序說明狸捅，當能用一種“化整為零”方法解決時可以試試另一種“循序漸進”的方法。

排序算法的復雜度

研究復雜度的第一步是建立一個計算模型累提。對排序來說尘喝，基于比較的算法對數(shù)組操作方式是由主鍵比較決定。

沒有任何基于比較的算法能保證使用少于 log(N!) ~ NlogN 次比較將長度為 N 的數(shù)組排序
歸并排序是一種漸進最優(yōu)的基于比較排序的算法刻恭。歸并排序在最壞情況下的比較次數(shù)和任意基于比較的排序算法所需的最少比較次數(shù)都是 ~NogN瞧省。

Q&A

1. 歸并排序比希爾排序快嗎扯夭？
   在實際應用中鳍贾，它們運行時間差距在常數(shù)級別。
2. 為什么不把數(shù)組 aux[] 聲明為 merge() 方法的局部變量交洗？
   為避免每次歸并時骑科，即使歸并很小的數(shù)組都創(chuàng)建一個新數(shù)組，否則創(chuàng)建新數(shù)組將成為歸并排序運行時間主要部分构拳。更好的方法是將 aux[] 變?yōu)?sort() 方法的局部變量咆爽，并作為參數(shù)傳給 merge() 方法。
3. 當數(shù)組中存在重復元素時歸并排序性能如何置森？
   若所有元素相同斗埂，則歸并排序運行時間是線性的。若有多個不同重復值凫海，運行時間是線性對數(shù)的（和所有元素都不重復滿足相同循環(huán)條件）呛凶。

1.5 快速排序

快速排序特點包括原地排序（只需一個很小的輔助棧），且將長度為 N 的數(shù)組排序所需時間和 NlogN 成正比行贪，內(nèi)循環(huán)比大多數(shù)排序算法都要短小漾稀。

快速排序：是一種分治排序算法。將一個數(shù)組分成兩個子數(shù)組建瘫，將兩部分獨立地排序崭捍。快排和歸并排序是互補的啰脚，歸并排序?qū)?shù)組分成兩個子數(shù)組分別排序殷蛇，并將有序的子數(shù)組歸并以將整個數(shù)組排序；快排的排序方式是當兩個子數(shù)組都有序時整個數(shù)組也自然有序了橄浓。前者的遞歸調(diào)用發(fā)生在處理整個數(shù)組之前粒梦；后者遞歸調(diào)用發(fā)生在處理整個數(shù)組之后。在歸并排序中贮配，一個數(shù)組被等分為兩半谍倦；在快排中，切分位置取決于數(shù)組的內(nèi)容泪勒。

public class Quick extends Example {
    public static void sort(Comparable[] a) {
        //消除對輸入的依賴
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);
        //將左半部分a[lo...j-1]排序
        sort(a, lo, j - 1);
        //將右半部分a[j+1...hi]排序
        sort(a, j + 1, hi);
    }
    private static int partition(Comparable[] a, int lo, int hi) {
        //將數(shù)組切分成a[lo...i-1], a[i], a[i+1...hi]
        //左右掃描指針
        int i = lo, j = hi + 1;
        //切分元素
        Comparable v = a[lo];
        while (true) {
            //掃描左右昼蛀，檢查掃描是否結(jié)束并交換元素
            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }
            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exch(a, i, j);
        }
        //將v = a[j]放入正確的位置
        exch(a, lo, j);
        //a[lo...j-1] <= a[j] <= a[j+1...hi]
        return j;
    }
}

快速排序最多需 N^2 / 2 次比較宴猾，但隨即打亂數(shù)組能預防這種情況。每次切分后兩子數(shù)組之一總是空的情況下比較次數(shù)為：N+(N-1)+...+1 = N(N+1) / 2叼旋，此時時間是平方級別的仇哆，空間是線性的。

快排改進

• 切換到插入排序夫植。對于小數(shù)組讹剔，快排比插入排序慢；因為遞歸详民，快排的sort()方法在小數(shù)組中也會調(diào)用自己延欠。因此在排序小數(shù)組時可切換到插入排序——將sort()中的 if (hi <= lo) return; 改為 if (hi <= lo + M){Insertion.sort(a, lo, hi); return;}，M 最佳值和系統(tǒng)相關沈跨，5~15之間通常較好由捎。
• 三取樣切分。使用子數(shù)組的一小部分元素的中位數(shù)來切分數(shù)組饿凛，這樣切分更好狞玛，代價是需計算中位數(shù)。
• 熵最優(yōu)的排序涧窒。實際應用經(jīng)常出現(xiàn)含有大量重復元素的數(shù)組心肪，一個元素全部重復的子數(shù)組就不需要繼續(xù)排序了，但之前的算法還會繼續(xù)切分成更小的數(shù)組纠吴。簡單的解決方法是將數(shù)組切分為三部分（詳見Dijkstra三向切分）硬鞍，分別對應小于、等于和大于切分元素的數(shù)組元素呜象，這種比目前二分更復雜膳凝，相關問題有荷蘭國旗問題。

三向切分示意圖

1. a[i] 小于 v恭陡，將 a[lt] 和 a[i] 交換蹬音，將 lt 和 i 加一
2. a[i] 大于 v，將 a[gt] 和 a[i] 交換休玩，將 gt減一
3. a[i] 等于 v著淆，將 i 加一

這些操作都會保證數(shù)組元素不變且縮小 gt-i 的值（這樣循環(huán)才會結(jié)束）。下面是三向切分的具體實現(xiàn)：

public class Quick3way{
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo){
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp < 0){
                exch(a, lt++, i++);
            }else if (cmp > 0){
                exch(a, i , gt--);
            }else {
                i++;
            }
            sort(a, lo, lt - 1);
            sort(a, gt + 1, hi);
        }
    }
}

對于只有若干不同主鍵的隨機數(shù)組拴疤，歸并排序時間復雜度是線性對數(shù)永部，而三向切分快排是線性的。對于任意分布的輸入呐矾，最優(yōu)的基于比較的算法平均所需比較次數(shù)和三向切分快排平均所需比較次數(shù)相互處于常數(shù)因子范圍內(nèi)苔埋。

《算法導論》上的快排

快排普通版本

public class QuickInCLRS extends Example {
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);
            sort(a, p, q - 1);
            sort(a, q + 1, r);
        }
    }
    private static int partition(Comparable[] a, int p, int r) {
        Comparable x = a[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (less(a[j], x)) {
                i++;
                exch(a, i, j);
            }
        }
        exch(a, i + 1, r);
        return i + 1;
    }
}

quicksort普通版本

快排隨機化版本

引入隨機性，可以使算法對于所有的輸入都能獲得較好的期望性能蜒犯。在快排中采用隨機抽樣的隨機化技術——從子數(shù)組 A[p...r] 中隨機選擇一個元素作為主元组橄。為此荞膘，可以將 A[r] 與從 A[p...r] 中隨機選出的一個元素交換來保證主元 x = A[r] 是等概率地從子數(shù)組的 r-p+1 個元素中獲取的。因為主元是隨機選的玉工，期望在平均情況下對輸入數(shù)組的劃分是比較均衡的羽资。

public class RandomQuickInCLRS extends QuickInCLRS {
    private static Random random = new Random();
    private static void sort(Comparable[] a, int p, int r) {
        if (p < r) {
            int q = randomPartition(a, p, r);
            sort(a, p, q - 1);
            sort(a, q + 1, r);
        }
    }
    private static int randomPartition(Comparable[] a, int p, int r) {
        //隨機選取主元，這里是獲取其位置
        int j = random.nextInt(r) + p;
        //隨機選出的主元與a[r]交換
        exch(a, j, r);
        return partition(a, p, r);
    }
}

快排時間復雜度

• 最壞情況：
  當劃分產(chǎn)生的兩個子問題分別包含了 n-1 個和 0 個元素時遵班，劃分時間復雜度為 O(n)屠升，因為對一個大小為 0 的數(shù)組進行遞歸調(diào)用會直接返回，因此 T(0) = O(1)狭郑，于是算法運行時間的遞歸式為：T(n) = T(n-1) + T(0) + O(n) = T(n-1)+O(n) = O(n^2)腹暖。此外，在輸入數(shù)組完全有序時愿阐，快排時間復雜度仍為 O(n^2)微服，而插入排序則為 O(n)。

• 最好情況：
  partition 得到的兩個子問題規(guī)模都不大于 n / 2缨历，子問題規(guī)模分別為 n / 2 和 n / 2 - 1，此時算法運行時間遞歸式為：T(n) = 2T(n / 2) + O(n) = O(nlogn)糙麦。

• 平衡的劃分：
  快排平均運行時間更接近于最好情況辛孵，而非最壞情況。如按 9:1 劃分赡磅，遞歸樹如下：

  
  
  quicksort遞歸樹

  只要劃分是常數(shù)比例的魄缚，算法的運行時間總是 O(nlogn)。

隨機化版本

1.6 優(yōu)先隊列

優(yōu)先隊列支持刪除最大元素和插入元素焚廊∫逼ィ基于二叉堆的優(yōu)先隊列，是用數(shù)組保存元素并按照一定條件排序咆瘟，以實現(xiàn)高效地（對數(shù)級別）刪除最大元素和插入元素嚼隘。優(yōu)先隊列實際應用包括模擬系統(tǒng)、任務調(diào)度和數(shù)值計算等袒餐。

通過插入一列元素然后一個個刪除其中的最小元素飞蛹，就可以用優(yōu)先隊列實現(xiàn)排序算法。堆排序來自于基于堆的優(yōu)先隊列的實現(xiàn)灸眼。

API

優(yōu)先隊列是一種抽象數(shù)據(jù)類型卧檐，表示了一組值和這些值的操作登刺。優(yōu)先隊列最重要操作是刪除最大元素和插入元素损谦，

public class MaxPQ<Key extends Comparable<Key>>
        MaxPQ()             //創(chuàng)建一個優(yōu)先隊列
        MaxPQ(int max)      //創(chuàng)建一個最大容量為 max 的優(yōu)先隊列
        MaxPQ(Key[] a)      //用a[]中的元素創(chuàng)建一個優(yōu)先隊列
        void insert(Key v)  //插入元素
        Key max()           //返回最大元素
        Key delMax()        //刪除并返回最大元素
        boolean isEmpty()   //返回隊列是否為空
        int size()          //返回優(yōu)先隊列中的元素個數(shù)

優(yōu)先隊列的調(diào)用示例

一個優(yōu)先隊列的用例

public static void main(String[] args){
    //打印輸入流中最大的M行
    int M = Integer.parseInt(args[0]);
    MinPQ<Transaction> pq = new MinPQ<Transaction>(M + 1);
    while(StdIn.hasNextLine()){
        //為下一行輸入創(chuàng)建一個元素并放入優(yōu)先隊列中
        pq.insert(new Transaction(StdIn.readLine()));
        //最大的M個元素都在優(yōu)先隊列中
        if(pq.size() > M){
            //若優(yōu)先隊列中存在M+1個元素則刪除最小的元素
            pq.delMin();
        }
    }
    Stack<Transaction> stack = new Stack<Transaction>();
    while(!pq.isEmpty()){
        stack.push(pq.delMin());
    }
    for(Transaction t : stack){
        StdOut.println(t);
    }
}

初級實現(xiàn)

從N個輸入找到最大M個元素.png

堆的定義

在二叉堆數(shù)組中，每個元素都要保證大于等于另兩個特定位置的元素驻右。相應地垒在，這些位置元素又至少大于等于數(shù)組中另兩個元素斜做。
堆有序：一棵二叉樹的每個結(jié)點都大于等于它的兩個子結(jié)點，根結(jié)點是堆有序的二叉樹中的最大結(jié)點湾揽。

二叉堆表示法

若用指針表示堆有序的二叉樹瓤逼，則每個元素都需三個指針來找它的父節(jié)點和兩個子節(jié)點霸旗。但若用完全二叉樹诱告，則可只用數(shù)組而不需指針精居。具體方法是將二叉樹的節(jié)點按層級順序放入數(shù)組靴姿，根節(jié)點在位置1磁滚，其子節(jié)點在位置2和3垂攘，而子節(jié)點的子節(jié)點分別在位置4,晒他、5仪芒、6和7掂名。

二叉堆是一組能用堆有序的完全二叉樹排序的元素饺蔑，并在數(shù)組中按層級存儲（不用數(shù)組第一個位置）

在一個堆（后文都指二叉堆），位置 k 的節(jié)點的父節(jié)點在 $\lfloor\frac{k}{2}\rfloor$隆敢，兩個子節(jié)點分別為 2k 和 2k+1拂蝎。

堆的表示

一棵大小為 N 的完全二叉樹的高度為 $\lfloor logN\rfloor$

堆的算法

堆實現(xiàn)的比較和交換方法：

private boolean less(int i, int j){
    return pq[i].compareTo(pa[j]) < 0;
}
private void exch(int i, int j){
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}

由下至上的堆有序化（上肝伦浴）

若堆的有狀態(tài)因某個節(jié)點變得比它的父節(jié)點更大而被打破悼泌，則需通過交換它和它的父節(jié)點來修復堆馆里。交換后鸠踪，該節(jié)點比它的兩個子節(jié)點都大慢哈。重復該過程，直到遇到更大的父節(jié)點侣集。

上浮

private void swim(int k){
    while(k > 1 && less(k/2, k)){
        exch(k/2, k);
        k = k/2;
    }
}

由上至下的堆有序化（下沉）

若堆的有序狀態(tài)因某個節(jié)點比它的兩個子節(jié)點或其中之一更小而被打破，則可通過將它和它的兩個子節(jié)點較大者交換來恢復堆臭埋。重復該過程瓢阴，直到它的子節(jié)點都比它更小或到達了堆的底部荣恐。

下沉

private void sink(int k){
    while(2*k <= N){
        int j = 2*k;
        if(j < N && less(j, j+1)){
            j++;
        }
        if(!less(k, j)){
            break;
        }
        exch(k, j);
        k = j;
    }
}

插入元素：將新元素加到數(shù)組末尾叠穆，增加堆的大小并讓該新元素上浮到合適位置硼被。

插入元素

刪除最大元素：從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個元素放到頂端检访，減小堆的大小并讓這個元素下沉到合適位置烛谊。

刪除最大元素

• 基于堆的優(yōu)先隊列

public class MaxPQ<Key extends Comparable<Key>> {
    /**
     * 基于堆的完全二叉樹
     */
    private Key[] pq;
    /**
     * 存儲于pq[1...N]中丹禀，pq[0]沒有使用
     */
    private int N = 0;
    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN + 1];
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }
    public Key delMax() {
        //從根節(jié)點得到最大元素
        Key max = pq[1];
        //pq[1] = pq[N--];
        //將其和最后一個節(jié)點交換
        exch(1, N--);
        //防止越界
        pq[N + 1] = null;
        sink(1);
        return max;
    }
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }
    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(j, j + 1)) {
                j++;
            }
            if (!less(k, j)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }
    private void show(){
        Stack<Key> stack = new Stack<>();
        while(!isEmpty()){
            stack.push(delMax());
        }
        for(Key t : stack){
            System.out.println(t);
        }
    }
     public static void main(String[] args) {
//        int[] a = new int[]{1,100,1,1, 26, 1,100,13, 27, 49, 55, 4};
        int[] a = new int[]{ 2 ,8, 2, 4, 3, 5, 2, 4};
         MaxPQ<Integer> maxPQ =  new MaxPQ<>(a.length);
         for (int i = 0; i < a.length; i++) {
            maxPQ.insert(a[i]);
         }
         maxPQ.show();
    }
}

命題：對于一個含有 N 個元素的基于堆的優(yōu)先隊列，插入元素操作只需不超過 lgN+1 次比較焙矛，刪除最大元素操作需要不超過 2lgN 次比較村斟。

證明：兩種操作都需要在根節(jié)點和堆底之間移動元素，而路徑長度不超過 lgN逾滥。對于路徑上的每個節(jié)點败匹，刪除最大元素需要兩次比較（除了堆底元素）舔哪，一次用來找出較大的子節(jié)點尸红，一次用來確定該子節(jié)點是否需要上浮外里。

多叉堆

完全三叉堆：對于數(shù)組中1至 N 的 N 個元素盅蝗，位置 k 的節(jié)點大于等于位于 3k-1、3k 和 3k+1 的節(jié)點，小于等于位于 (k+1) / 3的節(jié)點灌侣。需要在樹高 log_d(N) 和在每個節(jié)點的 d 個子節(jié)點找到最大者的代價之間找到折中侧啼，這取決于實現(xiàn)細節(jié)以及不同操作的預期相對頻繁程度痊乾。

調(diào)整數(shù)組大小

添加一個沒有參數(shù)的構(gòu)造函數(shù)哪审，在 insert() 中添加將數(shù)組長度加倍的代碼湿滓，在 delMax() 中添加將數(shù)組長度減半的代碼茉稠。

堆排序

可以把任意優(yōu)先隊列變成一種排序方法，將所有元素插入一個查找最小元素的優(yōu)先隊列恋日，然后再重復調(diào)用刪除最小元素的操作按順序刪除岂膳。用無序數(shù)組實現(xiàn)優(yōu)先隊列這么做相當于進行一次插入排序谈截，用堆實現(xiàn)得到堆排序簸喂。堆排序分兩個階段：

• 堆的構(gòu)造：將原始數(shù)組重新組織安排進一個堆中喻鳄。
• 下沉排序：從堆中按遞減順序取出所有元素并得到排序結(jié)果除呵。

堆的構(gòu)造

連續(xù)向優(yōu)先隊列插入元素可行纠拔，但更高效的方法是從右到左用 sink() 函數(shù)構(gòu)造子堆稠诲。數(shù)組每個位置都已經(jīng)是一個子堆的根節(jié)點了吕粹，sink() 對于這些子堆也適用匹耕。若一個節(jié)點的兩個子節(jié)點都已經(jīng)是堆了稳其，則在該節(jié)點上調(diào)用 sink() 可將它們變成一個堆既鞠。開始時只需掃描數(shù)組中一半元素嘱蛋，因為可以跳過大小為1的子堆。最后在位置1上調(diào)用 sink() 方法凶伙，掃描結(jié)束函荣。在排序第一階段傻挂，堆的構(gòu)造方法和我們潛意識想象的不同踊谋，因為我們目標是構(gòu)造一個堆有序的數(shù)組并使最大元素位于數(shù)組的開頭（次大的元素在附近）而非構(gòu)造函數(shù)結(jié)束的末尾殖蚕。

用下沉操作由 N 個元素構(gòu)造堆只需少于 2N 次比較以及少于 N 次交換

下沉排序

將堆中最大元素刪除睦疫，然后放入堆縮小后數(shù)組中空出的位置宛官，該過程和選擇排序類似（按降序而非升序取出所有元素）底洗，但因為堆提供了一種從未排序部分找到最大元素的有效辦法亥揖，所需比較次數(shù)少得多费变。

堆的構(gòu)造和下沉排序

public static void sort(Comparable[] a){
    //構(gòu)造堆
    int N = a.length;
    for(int k = N/2; k >= 1; k--){
        sink(a, k, N);
    }
    //下沉排序
    while(N > 1){
        exch(a, 1, N--);
        sink(a, 1, N);
    }
}

將N個元素排序，堆排序只需少于 2NlgN+2N 次比較（以及一半次數(shù)的交換）滑负，2N 項來自于堆的構(gòu)造橙困，2NlgN 來自于每次下沉操作最大可能需要 2lgN 次比較。

改進：先下沉后上浮

大多數(shù)在下沉排序期間重新插入堆的元素會被直接加入堆底夏跷。Floyd 1964 年發(fā)現(xiàn)可以通過免去檢查元素是否到達正確位置來節(jié)省時間槽华。在下沉中總是直接提升較大的子節(jié)點直至到達堆底猫态，然后再使元素上浮到正確位置亲雪，這樣可以將比較次數(shù)減少一半——接近了歸并排序所需比較次數(shù)（隨機數(shù)組）。該方法需額外空間灌砖，因此實際應用中只有當比較操作代價比較高時才用（例如：將字符串或其它鍵值較長類型的元素排序時）基显。

堆排序在排序復雜性研究中有重要地位撩幽，因為它是唯一能同時最優(yōu)地利用空間和時間的方法——最壞情況下能保證使用 ~2NlgN 次比較和恒定的額外空間。當空間十分緊張時（如嵌入式系統(tǒng)或低成本移動設備）很流行酱虎，因為它只用幾行就能實現(xiàn)較好的性能（甚至機器碼也是）读串。但現(xiàn)代系統(tǒng)很少用，因為它無法利用緩存杰捂。數(shù)組元素很少和相鄰的其它元素比較嫁佳，因此緩存未命中的次數(shù)要遠高于大多數(shù)比較都在相鄰元素間進行的算法蒿往，如快排瓤漏、歸并排序蝶俱、甚至是希爾排序跷乐。

在大數(shù)據(jù)量下愕提，要處理 TopK 和 Multiway 問題，無法排序（或無法全裝進內(nèi)存）如输，如 10 億元素中選最大 10 個，則只用一個能存儲十個元素的隊列即可稳吮。

1.7 排序算法和優(yōu)先隊列的應用

將各種數(shù)據(jù)排序

前面實現(xiàn)的排序?qū)ο笫怯蓪崿F(xiàn)了Comparable接口的對象組成的數(shù)組灶似，這樣可以利用 Java 的回調(diào)機制將任意實現(xiàn)了 Comparable接口的數(shù)據(jù)類型排序。實現(xiàn)Comparable接口只需定義一個compareTo()函數(shù)并在其中定義該數(shù)據(jù)類型的大小關系春感。Java 中的 String甥厦、Integer、Double谦秧、File 和 URL都實現(xiàn)了Comparable接口疚鲤。

指針排序

前面使用的方法被稱為指針排序，因為只處理元素的引用而不移動數(shù)據(jù)本身诲宇。在C/C++中姑蓝，需要明確指出操作的是數(shù)據(jù)還是指向數(shù)據(jù)的指針纺荧，在 Java 中，指針的操作是隱式的占贫。除了原始數(shù)字類型外，操作的總是數(shù)據(jù)的引用（指針）而非數(shù)據(jù)本身桩引。

不可變的鍵

若排序后用例還能修改鍵值，那么數(shù)組就不再有序了厘灼。Java 中可用不可變數(shù)據(jù)類型作為鍵來避免該問題夹纫，如String、Integer设凹、Double和 File 都是不可變的舰讹。

廉價的交換

使用引用另一個好處是可以不必移動整個元素。對于元素大而鍵小的數(shù)組來說節(jié)約是巨大的闪朱，因為比較只需訪問元素一小部分月匣，而排序過程大部分元素都不會被訪問到奋姿。對于幾乎任意大小的元素锄开，引用在一般情況下交換成本和比較成本幾乎相同（代價是需要額外空間存儲引用）。

多種排序方法

Java 的 Comparator 接口允許在一個類中實現(xiàn)多種排序方法称诗。它只有一個 compare() 方法來比較兩個對象萍悴，用 Comparator 接口代替Comparable接口可以將數(shù)據(jù)類型定義和兩個該數(shù)據(jù)類型的比較的定義區(qū)分開。例如 Insertion.sort(a, String.CASE_INSENSITIVE_ORDER)寓免，對 Transaction 對象數(shù)組按時間排序 Insertion.sort(a, new Transaction.WhenOrder())癣诱，按金額排序 Insertion.sort(a, new Transaction.HowMuchOrder()) 等。sort() 方法每次都會回調(diào) Transaction 類中的用例指定的 compare() 方法再榄，為避免每次排序都創(chuàng)建新的 Comparator 對象狡刘，使用 public final 來定義這些比較器（就像使用 String.CASE_INSENSITIVE_ORDER 一樣）

public static void sort(Object[] a, Comparator c){
    int N = a.length;
    for(int i = 1; i < N; i++){
        for(int j  = i; j > 0 && less(c, a[j], a[j-1]);j--){
            exch(a, j, j-1);
        }
    }
}
private static boolean less(Comparator c, Object v, Object w){
    return c.compare(v, w) < 0;
}
private static void exch(Object[] a, int i, int j){
    Object t = a[i];
    a[i] = a[j];
    a[j] = t;
}

使用比較器實現(xiàn)優(yōu)先隊列

• 為 MaxPQ 添加一個實例變量 comparator 以及一個構(gòu)造函數(shù)，該構(gòu)造函數(shù)接受一個比較器作為參數(shù)并用它將 comparator 初始化困鸥。
• 在 less() 中檢查 comparator 屬性是否為 null（如果不是就用它比較）

使用了 Comparator 的插入排序：

public class Transaction{
    private final String who;
    private final Date when;
    private final Double amount;
    public static class WhoOrder implements Comparator<Transaction>{
        public int compare(Transaction v, Transaction w){
            return v.who.compareTo(w.who);
        }
    }
    public static class WhenOrder implements Comparator<Transaction>{
        public int compare(Transaction v, Transaction w){
            return v.when.compareTo(w.when);
        }
    }
    public static class HowMuchOrder implements Comparator<Transaction>{
        public int compare(Transaction v, Transaction w){
            if(v.amount < w.amount) return -1;
            if(v.amount > w.amount) return 1;
            return 0;
        }
    }
}

穩(wěn)定性

若一個排序算法能保留數(shù)組中重復元素的相對位置則可被稱為穩(wěn)定的嗅蔬。一部分算法是穩(wěn)定的——插入排序和歸并排序，但選擇排序疾就、希爾排序澜术、快速排序和堆排序不穩(wěn)定。

該用哪種排序

各種排序算法的性能特點

快排是最快的通用排序算法

問題規(guī)約

在使用解決問題 B 的方法來解決問題 A 時猬腰，都在將 A 規(guī)約為 B鸟废。

找出重復元素

在一個 Comparable 對象的數(shù)組中是否存在重復元素？有多少重復元素姑荷？哪個值出現(xiàn)最頻繁盒延？

通過兩兩比較可以在平方級別解決，但通過排序可在線性對數(shù)時間內(nèi)解決鼠冕。

Quick.sort(a);
int count = 1;
for(int i = 1; i < a.length; i++){
    if(a[i].compareTo(a[i-1])!=0){
        count++;
    }
}

排名

逆序?qū)?shù)問題

中位數(shù)與順序統(tǒng)計

一個和排序有關但又不需要完全的重要應用就是找出一組元素的中位數(shù)添寺，有一種特殊選擇：找到一組數(shù)中第 k 小的元素。通過前面的 TopM 問題用優(yōu)先隊列可以解決懈费，或者排序后獲取第 k 個元素也可以解決计露，但都是線性對數(shù)時間。實際上，當 k 很小或很大時可以在線性時間找到：

public static Comparable select(Comparable[] a, int k){
    StdRandom.suhffle(a);
    int lo = 0, hi = a.length - 1;
    while(hi > lo){
        int j = partition(a, lo, hi);
        if(j == k){
            return a[k];
        }else if(j > k){
            hi = j - 1;
        }else{
            lo = j + 1;
        }
    }
    return a[k];
}

不斷切分知道子數(shù)組只含有第 k 個元素票罐，此時 a[k] 含有最小的（k+1）個元素叉趣，a[0] 到 a[k-1] 都小于等于 a[k]，而 a[k+1] 及其后的元素都大于等于 a[k]该押。假設每次都正好將數(shù)組二分疗杉，則比較總次數(shù)是（N+N/2+N/4+...）直到找到第 k 個元素，根據(jù)等比數(shù)列求和公式該和顯然小于 2N蚕礼。

平均來說乡数，基于切分的選擇算法運行時間是線性級別的。

本篇介紹的算法的完整代碼地址：
代碼地址

以下是可供參考的博客：
各種排序算法時間復雜度
面試中的排序算法總結(jié)
八大排序算法
必須知道的八大種排序算法【java實現(xiàn)】
坐在馬桶上看算法：快速排序