摘要：本文對種排序方法進(jìn)行匯總。自頂向下的歸并排序算法歸并排序自頂向下分治思想的最經(jīng)典的一個例子。另外，快排序的內(nèi)循環(huán)比大多數(shù)排序算法都短?；舅惴炫判蚴且环N分治的算法，將一個數(shù)組分成兩個子數(shù)組，將兩部分獨立排序。

本文對9種排序方法進(jìn)行匯總。
分別是： 插入排序 選擇排序 歸并排序 冒泡排序 堆排序 快排序 計數(shù)排序 基數(shù)排序 桶排序。
參照《算法》第四版這本書，把排序需要的公共的方法抽象出來，做一個抽象類，討論到的各個排序類對抽象類進(jìn)行繼承，只需關(guān)注與排序本身的業(yè)務(wù)邏輯即可。
https://visualgo.net/sorting

抽象出來的父類為：

abstract Sort{
    abstract void sort(array);     // 需要被實現(xiàn)
    void exchange(array, i, j);    // 交換數(shù)組中的i 和j位置的元素
    boolean less(a, b);            // a是否小于b
    boolean isSorted(array);       // 數(shù)組是否已排好序
    void test(arr);                // 對傳入的數(shù)組進(jìn)行測試
}

對應(yīng)的Java實現(xiàn)

/**
 1. 排序的抽象類
 2.         可以接受任意類型，可以自定義比較器
 3. @param 
 */
public abstract class Sort {
    /** 測試數(shù)組，這里為了方便使用整型數(shù)組*/
    protected static Integer[] testArray = { 3, 2, 5, 1, 4, 7 ,10};
    /** 繼承該類需要實現(xiàn)排序方法*/
    public abstract void sort(Comparable[] array);
    /** 交換數(shù)組元素的業(yè)務(wù)方法*/
    protected void exchange(Comparable[] array, int i, int j){
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    /** 比較兩個元素的方法*/
    protected boolean less(Comparable a, Comparable b){
        return a.compareTo((T) b) < 0;
    }
    /** 判斷數(shù)組是否已排序的方法*/
    protected boolean isSorted(Comparable[] array){
        for(int i = 1; i[] arr){
        //輸出排序前的數(shù)組
        System.out.println(Arrays.toString(arr));
        //排序
        sort(arr);
        //輸出排序后的結(jié)果
        System.out.println(Arrays.toString(arr));
        //輸出是否已經(jīng)排序
        System.out.println("是否已經(jīng)排序：" + isSorted(arr));
    }
}

時間O(n^2);空間O(1)；

排序時間與輸入有關(guān)：輸入的元素個數(shù)，輸入元素已排序程度；

最好情況：輸入數(shù)組已經(jīng)是排序的，時間變?yōu)閚的線性函數(shù)；

最壞情況：輸入數(shù)組是逆序，時間是n的二次函數(shù)

/**
 * 插入排序
 */
public class InsertSort extends Sort {
    @Override
    public void sort(Comparable[] array) {
        int len = array.length;
        // 把a[i] 插入到a[i-1], a[i-2], a[i-3]...中
        for (int i = 1; i < len; i++) {
            // j從i開始，如果j>0并且j處元素比前面的元素小，則進(jìn)行交換，j--，繼續(xù)向前比較
            for (int j = i; j > 0 && less(array[j], array[j-1]); j--)
                exchange(array, j, j-1);
        }
    }

    public static void main(String[] args) {
        new InsertSort().test(testArray);
    }
}

結(jié)果：

[3, 2, 5, 1, 4, 7, 10]
[1, 2, 3, 4, 5, 7, 10]
是否已經(jīng)排序：true

時間O(n^2),空間O(1)

排序時間和輸入無關(guān)

最好和最壞都是一樣的

不穩(wěn)定，例如{6, 6, 1}.找到最小的是1，和第一個6交換以后，第一個6跑到了后面.

/**
 * 選擇排序
 */
public class SelectionSort extends Sort{
    @Override
    public void sort(Comparable[] array) {
        int len = array.length;
        for(int i = 0; i

3.歸并排序

歸并排序的所有算法都基于歸并這個簡單的操作，即將兩個有序的數(shù)組歸并稱為一個更大的有序數(shù)組。

發(fā)現(xiàn)這個算法的由來：要將一個數(shù)組排序，可以先遞歸地將它分成兩半分別排序，然后將結(jié)果歸并起來。

性質(zhì)：能夠保證將任意長度為N的數(shù)組排序，所需時間和NlogN成正比；

缺點：所需額外空間和N成正比。

排序時間和輸入無關(guān)，最佳情況最壞情況都是如此，穩(wěn)定。


3.1自頂向下的歸并排序算法
/**
* 歸并排序：自頂向下
*         分治思想的最經(jīng)典的一個例子。
*         這段遞歸代碼是歸納證明算法能夠正確地將數(shù)組排序的基礎(chǔ)：
*             如果它能將兩個子數(shù)組排序，它就能通過歸并兩個子數(shù)組來講整個數(shù)組排序
*/
public class MergeSort extends Sort{
    private static Comparable[] auxiliary;
    @Override
    public void sort(Comparable[] array) {
        auxiliary = new Comparable[array.length];
        sort(array, 0, array.length-1);
    }
    
    private void sort(Comparable[] array, int low, int high) {
        if(high <= low)        return;
        int mid = low + (high - low) / 2;
        sort(array, low, mid);        //將左半邊排序
        sort(array, mid + 1, high);    //將右半邊排序
        merge(array, low, mid, high);//歸并結(jié)果
    }

    private void merge(Comparable[] a, int low, int mid, int high){
        // 將a[low...mid]和a[mid+1...high]歸并
        int i = low, j = mid + 1;
        // 先將所有元素復(fù)制到aux中，然后再歸并會a中。
        for(int k = low; k <= high; k++)
            auxiliary[k] = a[k];
        for(int k = low; k <= high; k++)//歸并回到a[low...high]
            if(i > mid)    
                a[k] = auxiliary[j++];    // 左半邊用盡，取右半邊的元素
            else if    (j > high)
                a[k] = auxiliary[i++];    // 右半邊用盡，取左半邊的元素
            else if    (less(auxiliary[j], auxiliary[i]))
                a[k] = auxiliary[j++];    // 右半邊當(dāng)前元素小于左半邊當(dāng)前元素，取右半邊的元素
            else    
                a[k] = auxiliary[i++];    // 左半邊當(dāng)前元素小于又半邊當(dāng)前元素，取左半邊的元素
    }
    public static void main(String[] args) {
        new MergeSort().test(testArray);
    }
}
對于16個元素的數(shù)組，其遞歸過程如下：

這個NLogN的時間復(fù)雜度和插入排序和選擇排序不可同日而語，它表明只需比遍歷整個數(shù)組多個對數(shù)因子的時間就能將一個龐大的數(shù)組排序?？梢杂脷w并排序處理百萬甚至更大規(guī)模的數(shù)組，這是插入和選擇排序所做不到的。
其缺點是輔助數(shù)組所使用的額外空間和N的大小成正比。
另外通過一些細(xì)致的思考，還可以大幅度縮短歸并排序的運行時間。

考慮1：對小規(guī)模子數(shù)組使用插入排序。使用插入排序處理小規(guī)模的子數(shù)組（比如長度小于15）一般可以將歸并排序運行時間縮短10%-15%。

考慮2：測試數(shù)組是否已經(jīng)有序?？梢蕴砑右粋€判斷條件，如果array[ mid ] <= array[ mid + 1 ]就認(rèn)為數(shù)組已經(jīng)是有序的，并跳過merge方法，這個改動不影響排序的遞歸調(diào)用，但是任意有序的子數(shù)組算法運行的時間就變成線性了。

考慮3：不將元素復(fù)制到輔助數(shù)組?？梢怨?jié)省將元素復(fù)制到用于歸并的輔助數(shù)組所用的時間（但空間不行）。要做到這一點需要調(diào)用兩種排序方法，一種將數(shù)據(jù)從輸入屬豬排序到輔助數(shù)組，一種將數(shù)據(jù)從輔助數(shù)組排序到輸入數(shù)組。



3.2 自底向上的歸并排序
先歸并那些微型數(shù)組，然后再成對歸并得到的子數(shù)組，如此這般，直到將整個數(shù)組歸并在一起。
該實現(xiàn)比標(biāo)準(zhǔn)遞歸方法代碼量少。
首先進(jìn)行兩兩歸并，然后四四歸并，八八歸并，一直下去。在每一輪歸并中，最后一次歸并的第二個子數(shù)組可能比第一個要小，但是對merge方法不是問題，如果不是的話所有的歸并中兩個數(shù)組的大小都應(yīng)該一樣，而在下一輪中子數(shù)組的大小翻倍。如圖：

/**
 * 自底向上的歸并排序
 *         會多次遍歷整個數(shù)組，根據(jù)子數(shù)組大小進(jìn)行兩兩歸并。
 *         子數(shù)組的大小size初始值為1，每次加倍。
 *         最后一個子數(shù)組的大小只有在數(shù)組大小是size的偶數(shù)被時才會等于size，否則會比size小。
 * @param 
 */
public class MergeSortBU extends Sort{
    private static Comparable[] aux;
    @Override
    public void sort(Comparable[] a) {
        int n = a.length;
        aux = new Comparable[n];
        //進(jìn)行l(wèi)gN次兩兩歸并
        for(int size = 1; size < n; size = size + size)
            for(int low = 0; low < n - size; low += size+size)
                merge(a, low, low+size-1, Math.min(low+size + size-1, n-1));
    }
    @SuppressWarnings("unchecked")
    private void merge(Comparable[] a, int low, int mid, int high){
        int i = low, j = mid + 1;
        for(int k = low; k <= high; k++)
            aux[k] = a[k];
        for(int k = low; k <= high; k++){
            if(i > mid)
                a[k] = aux[j++];
            else if(j > high)
                a[k] = aux[i++];
            else if(less(a[j], a[i]))
                a[k] = aux[j++];
            else
                a[k] = aux[i++];
        }
    }
    public static void main(String[] args) {
        new MergeSortBU().test(testArray);
    }
}
如果是排序16個元素的數(shù)組，過程如下圖

4.冒泡排序
比較簡單
/**
 * 冒泡排序
 * 時間：O(n^2)；空間O(1)
 * 穩(wěn)定，因為存在兩兩比較，不存在跳躍
 * 排序時間與輸入無關(guān)
 */
public class BubbleSort extends Sort {
    @Override
    public void sort(Comparable[] array) {
        int len = array.length;
        for(int i = 0; ii; j--){
                if(less(array[j], array[j-1]))
                    exchange(array, j, j-1);
            }
        }
    }
    public static void main(String[] args) {
        new BubbleSort().test(testArray);
    }
}
缺陷：

排序過程中，執(zhí)行完第i趟排序后，可能數(shù)據(jù)已全部排序完畢，但是程序無法判斷是否完成排序，會繼續(xù)執(zhí)行剩下的(n-1-i)趟排序。解決方法：設(shè)置一個flag位，如果一趟無元素交換，則flag=0；以后再也不進(jìn)入第二層循環(huán)。

當(dāng)排序的數(shù)據(jù)比較多時，排序的時間會明顯延長，因為會比較n*(n-1)/2次。



5. 快排序
快排序
實現(xiàn)簡單，適用于各種不同輸入，一般應(yīng)用中比其他算法快很多。

特點：原地排序（只需很小的一個輔助棧）；時間和NlgN成正比。同時具備這兩個優(yōu)點。
        另外，快排序的內(nèi)循環(huán)比大多數(shù)排序算法都短。
5.1 基本算法
快排序是一種分治的算法，將一個數(shù)組分成兩個子數(shù)組，將兩部分獨立排序。
快排序和歸并排序互補：歸并排序?qū)?shù)組分成兩個子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個數(shù)組排序；
而快排序?qū)?shù)組排序的方式是當(dāng)兩個子數(shù)組都有序的時候，整個數(shù)組自然也就有序了。
第一種情況，遞歸調(diào)用發(fā)生在處理整個數(shù)組之前；第二種情況，遞歸發(fā)生在處理整個數(shù)組之后。
歸并排序中，一個數(shù)組被等分為兩半；快排序中，切分的位置取決于數(shù)組的內(nèi)容。

/**
 * 快排序
 */
public class QuickSort extends Sort {
    @Override
    public void sort(Comparable[] array) {
        shuffle(array);
        System.out.println("打亂后:"+Arrays.toString(array));
        sort(array, 0, array.length - 1);
    }
    private void sort(Comparable[] array, int low, int high) {
        if(high <= low)    return;
        int j = partition(array, low, high);    // 切分
        sort(array, low, j-1);            // 將左半部分array[low, ... , j-1]進(jìn)行排序
        sort(array, j+1, high);            // 將右半部分array[j+1, ... , high]進(jìn)行排序
    }
    private int partition(Comparable[] array, int low, int high) {
        // 將數(shù)組切分為array[low, ... , i-1], array[i], array[i+1, ... , high]
        int i = low, j = high+1;        //左右掃描指針
        Comparable v = array[low];    
        while(true){
            //掃描左右，檢查掃描是否結(jié)束并交換元素
            while(less(array[++i], v))    if(i == high)    break;//左指針向右找到一個大于v的位置
            while(less(v, array[--j]))    if(j == low)    break;//右指針向左找到一個小于v的位置
            if(i >= j)    break;    // 如果左指針重疊或者超過右指針，跳出
            exchange(array, i, j);  // 交換左右指針位置的元素
        }
        exchange(array, low, j);
        return j;
    }
    private void shuffle(Comparable[] a){
        Random random = new Random();
        for(int i = 0; i().test(testArray);
    }
}
這段代碼按照array[low] 的值v進(jìn)行切分。當(dāng)指針i和j相遇時主循環(huán)退出。在循環(huán)中，array[i]小于v時，增大i，a[j]大于v時，減小j，然后交換array[i]和array[j]來保證i左側(cè)的元素都不大于v，j右側(cè)的元素都不小于v。當(dāng)指針相遇時交換array[low]和array[j],切分結(jié)束，這樣切分值就留在array[j]中了。


5.2快排序算法的改進(jìn)：
如果排序代碼會被執(zhí)行很多次，或者會被用在大型數(shù)組上（特別是如果被發(fā)布成一個庫函數(shù)，排序的對象數(shù)組的特性是未知的），那么需要提升性能。
以下改進(jìn)會將性能提升20%~30%。
切換到插入排序


對于小數(shù)組，快排序比插入排序慢

因為遞歸，快排序的Sort方法在小數(shù)組中也會調(diào)用自己
基于這兩點可以改進(jìn)快排序。改動以上算法，將sort()方法中的語句


if(high <= low) return ;
替換為：
if(high <= low + M) { Insersion.sort(array, low, high);  return; }
轉(zhuǎn)換參數(shù)M的最佳值和系統(tǒng)相關(guān)，5~15之間的任意值在大多情況下都令人滿足。
三取樣切分
使用子數(shù)組的一小部分元素的中位數(shù)來切分?jǐn)?shù)組。這樣做得到的切分更好，但是代價是需要計算中位數(shù)。

發(fā)現(xiàn)將取樣大小設(shè)置為3并用大小居中的元素切分的效果最好。
還可以將取樣元素放到數(shù)組末尾作為哨兵來去掉partition()中的數(shù)組邊界測試。
熵最優(yōu)的排序
在有大量重復(fù)元素的情況下，快速排序的遞歸性會使元素全部重復(fù)的子數(shù)組經(jīng)常出現(xiàn)，這樣就有很大的改進(jìn)潛力，能提高到線性級別。

簡單的想法：將數(shù)組且分為3部分，分別對應(yīng)小于，等于和大于切分元素的數(shù)組袁術(shù)。這種切分實現(xiàn)起來比目前的二分法更復(fù)雜。
/**
 * 快排序:三項切分的快速排序
 */
public class Quick3WaySort extends Sort {
    @Override
    public void sort(Comparable[] array) {
        shuffle(array);
        System.out.println("打亂后:"+Arrays.toString(array));
        sort(array, 0, array.length - 1);
    }
    private void sort(Comparable[] array, int low, int high) {
        if(high <= low)    return;
        int lt = low, i = low + 1, gt = high;
        Comparable v = array[low];
        while(i <= gt){
            int cmp = array[i].compareTo(v);
            if(cmp < 0)        exchange(array, lt++, i++);
            else if(cmp > 0)    exchange(array, i, gt--);
            else            i++;
        } // 現(xiàn)在array[low ... lt-1] < v = a[lt ... gt] < array[gt+1 .. high]成立
        sort(array, low, lt-1);
        sort(array, gt+1, high);
    }
    private void shuffle(Comparable[] a){
        Random random = new Random();
        for(int i = 0; i().test(chars);
    }
}

6.堆排序
時間復(fù)雜度O(nlogn)， 空間復(fù)雜度O(1)， 是一種原地排序。
排序時間和輸入無關(guān)，不穩(wěn)定。
對于大數(shù)據(jù)處理：如果對于100億條數(shù)據(jù)選擇 top K 的數(shù)據(jù)，只能用堆排序。堆排序只需要維護一個k大小的空間，即在內(nèi)存開辟k大小的空間。
而不能選擇快速排序，因為快排序要開辟1000億條數(shù)據(jù)的空間，這個是不可能的。
這里先來看算法第四版這本書中的2.4節(jié)：優(yōu)先級隊列
應(yīng)用舉例：絕大多數(shù)手機分配給來電的優(yōu)先級都會比其他應(yīng)用高。
數(shù)據(jù)結(jié)構(gòu)：優(yōu)先級隊列，需支持兩種操作 刪除最大元素和插入元素。
本節(jié)中簡單討論優(yōu)先級隊列的基本表現(xiàn)形式，其一或者兩種操作都能在線性時間內(nèi)完成。之后學(xué)習(xí)基于二叉堆結(jié)構(gòu)的一中優(yōu)先級隊列的經(jīng)典實現(xiàn)方法，
用數(shù)組保存元素并按照一定條件排序，以實現(xiàn)高效刪除最大元素和插入元素的操作（對數(shù)級別）。
堆排序算法也來自于基于堆的優(yōu)先級隊列的實現(xiàn)。

稍后學(xué)習(xí)用優(yōu)先級隊列構(gòu)造其他算法。

也能恰到好處的抽象若干重要的圖搜索算法（算法第四版第四章）。

也可以開發(fā)出一種數(shù)據(jù)壓縮算法（算法第四版第五章）。


6.1API的設(shè)計

三個構(gòu)造函數(shù)使得用例可以構(gòu)造制定大小的優(yōu)先級隊列，還可以用給定的一個數(shù)組將其初始化。
會在適當(dāng)?shù)牡胤绞褂昧硪粋€類MinPQ, 和MaxPQ類似，只是含有一個delMin()方法來刪除并返回最小元素。
MaxPQ的任意實現(xiàn)都能很容易轉(zhuǎn)化為MinPQ的實現(xiàn)，反之亦然，只需要改變一下less()比較的方向即可。
優(yōu)先級隊列的調(diào)用示例
為了展示優(yōu)先級隊列的價值，考慮問題：輸入N個字符串，每個字符串都對應(yīng)一個整數(shù)，找出最大的或最小的M個整數(shù)（及其關(guān)聯(lián)的字符串）。
例如：輸入金融事務(wù)，找出最大的那些；農(nóng)產(chǎn)品中殺蟲劑含量，找出最小的那些。。。
某些場景中，輸入量可能是巨大的，甚至可以認(rèn)為輸入是無限的。
解決這個問題，

一種方法是將輸入排序，然后從中找出M個最大元素。

另一種方法，將每個新的輸入和已知的M個最大元素比較，但除非M較小，否則這種比較代價高昂。

使用優(yōu)先級隊列，這種才是正解，只要高效的實現(xiàn)insert和delMin方法即可。
三種方法的成本：



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

命令行輸入一個整數(shù)M以及一系列字符串，每一行表示一個事務(wù)，代碼調(diào)用MinPQ并打印數(shù)字最大的M行。
初級實現(xiàn)：可以使用有序數(shù)組，無序數(shù)組，鏈表。

堆的定義：二叉堆能夠很好的實現(xiàn)優(yōu)先級隊列的基本操作。

當(dāng)一顆二叉樹的每個結(jié)點都大于等于它的兩個子結(jié)點時，被稱為堆有序。

根節(jié)點是堆有序的二叉樹中的最大節(jié)點。
二叉堆：一組能夠用堆有序的完全二叉樹排序的元素，并在數(shù)組中按層級存儲（不使用數(shù)組的第0個位置）


在一個堆中，位置K的節(jié)點的父節(jié)點位置為 K/2 向下取整，兩個子節(jié)點的位置分別是2K和2K+1。這樣可以在不使用指針的情況下通過計算數(shù)組的索引在樹中上下移動：從a[k]向上一層，就令k =  k/2,向下一層就令k = 2k 或者2k+1。

用數(shù)組實現(xiàn)的完全二叉樹結(jié)構(gòu)嚴(yán)格，但其靈活性足以讓我們高效的實現(xiàn)優(yōu)先級隊列。
能夠?qū)崿F(xiàn)對數(shù)級別的插入元素和刪除最大元素的操作。利用數(shù)組無需指針即可沿著樹上下移動的遍歷和以下性質(zhì)，保證了對數(shù)復(fù)雜度的性能。
命題：一顆大小為N的完全二叉樹的高度為lgN向下取整。
堆的算法：

用長度為N+1的私有數(shù)組pq[]來表示一個大小為N的堆，不使用pq[0]，對元素放在pq[1]—pq[n]中。

在之前的排序中，通過輔助函數(shù)less和exchange函數(shù)來訪問元素，但因為所有的元素都在數(shù)組pq中，該實現(xiàn)為了更加緊湊，不再將數(shù)組作為參數(shù)傳遞。

堆的操作首先進(jìn)行一些簡單的改動，打破堆的狀態(tài)，然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù)。這個過程叫做堆的有序化（reheapifying）


比較和交換方法：

可能遇到的兩種情況：
由下至上的堆有序化（上?。?br>如果堆的有序狀態(tài)因為某個節(jié)點變得比它的父節(jié)點更大而被打破，那么需要通過交換它和父節(jié)點位置來修復(fù)堆。交換后，這個節(jié)點比它的兩個子節(jié)點都大，但是仍然可能比它現(xiàn)在的父節(jié)點大，可以一遍遍的用同樣的方法恢復(fù)秩序，這個節(jié)點不斷上移知道遇到一個更大的父節(jié)點。只要記住位置K的節(jié)點的父節(jié)點的位置是K/2，該過程實現(xiàn)簡單。

由上至下的堆有序化（下沉）
如果有序狀態(tài)因為某個節(jié)點變得比兩個子節(jié)點或是其中之一更小而被打破，那么可以通過將它和兩個子節(jié)點中的較大者交換來恢復(fù)有序狀態(tài)。交換可能會在子節(jié)點出繼續(xù)打破有序狀態(tài)，因此需要不斷用相同方法來修復(fù)，將節(jié)點向下移動知道它的子節(jié)點都比它更小或者到達(dá)了對的地步。由位置K的節(jié)點的子節(jié)點位于2K和2K+1處，可以實現(xiàn)代碼。
例子：可以想象堆是一個嚴(yán)密的黑社會組織，每個子節(jié)點都表示一個下屬，父節(jié)點表示它的直接上級。swim表示一個很有能力的新人加入組織并被逐級提升（將能力不夠的上級踩在腳下），直到遇到一個更強的領(lǐng)導(dǎo)。sink則類似于整個社團的領(lǐng)導(dǎo)退休并被外來者取代后，如果他的下屬比他更厲害，他們的角色就會交換，這種交換會持續(xù)下去直到他的能力比其他下屬都強為止。
sink和swim方法是高效實現(xiàn)優(yōu)先級隊列API的基礎(chǔ)。

插入元素：新元素加到數(shù)組末尾；增加堆的大小；新元素上浮到合適的位置。
刪除最大元素：從數(shù)組頂端刪去最大的元素；并將數(shù)組的最后一個元素放到頂端；減小堆的大??；并讓該元素下沉到合適的位置。
該算法對API的實現(xiàn)能夠保證插入元素和刪除最大元素這兩個操作的用時和隊列大小僅呈對數(shù)關(guān)系。

命題：對于一個含有N個元素的基于堆的優(yōu)先級隊列，插入元素操作只需要不超過lgN+1次比較，刪除最大元素的操作需要不超過2lgN次比較。兩種操作都需要在根節(jié)點和堆底之間移動元素，而路徑的長度不超過lgN。對于路徑上的每個節(jié)點，刪除最大元素需要比較兩次（除了堆底元素），一次用來找出較大的子節(jié)點，一次用來確定該子節(jié)點是否需要上浮。
多叉堆

構(gòu)建完全三叉樹結(jié)構(gòu)
調(diào)整數(shù)組大小

添加無參構(gòu)造函數(shù)，在insert中添加將數(shù)組加倍的代碼，在delMax中添加將數(shù)組長度減半的代碼。
元素的不可變性

優(yōu)先級隊列存儲了用例創(chuàng)建的對象，但同時假設(shè)用例代碼不會改變它們。可將這個假設(shè)轉(zhuǎn)化為強制條件，但增加代碼的復(fù)雜性會降低性能。
索引優(yōu)先級隊列


很多應(yīng)用中，允許用例引用已進(jìn)入優(yōu)先級隊列中的元素很有必要。

做到這一點的一種簡單方法是給每個元素一個索引。

另外，一種常見的情況是用例已經(jīng)有了總量為N的多個元素，而且可能還同時使用了多個平行數(shù)組來存儲這些元素的信息。此時其他無關(guān)的用例代碼可能已經(jīng)在使用一個整數(shù)索引來引用這些元素了。
這些考慮引導(dǎo)我們設(shè)計了下列API。



將它看成一個能夠快速訪問其中最小元素的數(shù)組。
事實上還更好：能夠快速訪問數(shù)組的一個特定子集中的最小元素（指所有被插入的元素）。
換句話說：

可將名為pq的IndexMinPQ類優(yōu)先級隊列看做數(shù)組pq[0...n-1]中的一部分元素的代表。

將pq.insert(k,item)看做將k加入這個子集并使得pq[k]=item,

pq.change(k, item)則代表令pq[k]=item。

這兩種操作沒有改變其他操作所依賴的數(shù)據(jù)結(jié)構(gòu)，其中最重要的就是delMin()（刪除最小元素并返回它的索引）和change()（改變數(shù)據(jù)結(jié)構(gòu)中的某個元素的索引—即pq[i]=item）。這些操作在許多應(yīng)用中都很重要并且依賴于對元素的引用（索引）
命題：在一個大小為N的索引優(yōu)先級隊列中，插入元素insert、改變優(yōu)先級change、刪除delete和刪除最小元素remove the minimum 這些操作所需的比較次數(shù)和lgN成正比。



此處留坑，以后再看，這是庫中的源碼
/**
 * 索引優(yōu)先級隊列IndexMinPQ
 */
public class IndexMinPQ> implements Iterable {
    private int maxN;        // maximum number of elements on PQ
    private int n;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i
    public IndexMinPQ(int maxN) {
        this.maxN = maxN;
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
        pq  = new int[maxN + 1];
        qp  = new int[maxN + 1];                   // make this of length maxN??
        for (int i = 0; i <= maxN; i++)
            qp[i] = -1;
    }
    public boolean isEmpty() {return n == 0;}

    public boolean contains(int i) {return qp[i] != -1;}

    public int size() { return n;}

    public void insert(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        n++;
        qp[i] = n;
        pq[n] = i;
        keys[i] = key;
        swim(n);
    }
    public int minIndex() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    public Key minKey() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];
    }

    public int delMin() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        int min = pq[1];
        exch(1, n--);
        sink(1);
        assert min == pq[n+1];
        qp[min] = -1;        // delete
        keys[min] = null;    // to help with garbage collection
        pq[n+1] = -1;        // not needed
        return min;
    }

    public Key keyOf(int i) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }

    public void changeKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

    public void decreaseKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) <= 0)
            throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
        keys[i] = key;
        swim(qp[i]);
    }

    public void increaseKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) >= 0)
            throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
        keys[i] = key;
        sink(qp[i]);
    }

    public void delete(int i) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }


    private boolean greater(int i, int j) {return keys[pq[i]].compareTo(keys[pq[j]]) > 0;}

    private void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
    private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
    public Iterator iterator() { return new HeapIterator(); }

    private class HeapIterator implements Iterator {
        // create a new pq
        private IndexMinPQ copy;
        // add all elements to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            copy = new IndexMinPQ(pq.length - 1);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i], keys[pq[i]]);
        }

        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }
    }

    public static void main(String[] args) {
        // insert a bunch of strings
        String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
        IndexMinPQ pq = new IndexMinPQ(strings.length);
        for (int i = 0; i < strings.length; i++) 
            pq.insert(i, strings[i]);
        // delete and print each key
        while (!pq.isEmpty()) {
            int i = pq.delMin();
            StdOut.println(i + " " + strings[i]);
        }
        StdOut.println();
        // reinsert the same strings
        for (int i = 0; i < strings.length; i++) 
            pq.insert(i, strings[i]);
        // print each key using the iterator
        for (int i : pq) 
            StdOut.println(i + " " + strings[i]);
    }
}
索引優(yōu)先級隊列用例：
多向歸并問題：將多個有序的輸入流歸并成一個有序的輸入流。

輸入流可能來自多種一起的輸出（按時間排序），

或者來自多個音樂或電影網(wǎng)站的信息列表（按名稱或者藝術(shù)家名字排序），

或是商業(yè)交易（按賬號或時間排序）。

如果有足夠的空間，可以簡單地讀入一個數(shù)組并排序，但用了優(yōu)先級隊列無論輸入有多長你都可以把它們?nèi)孔x入并排序。


/**
 * 使用優(yōu)先隊列的多項歸并
 */
public class Multiway {
    public static void merge(In[] streams){
        int n = streams.length;
        IndexMinPQ pq = new IndexMinPQ(n);
        for(int i = 0;i
結(jié)果
A A B B B C D E F F G H I I J N P Q Q Z 

結(jié)果有了上面的擴展知識，下面來看堆排序：
可以把任意優(yōu)先級隊列變成一種排序方法。將所有元素插入一個查找最小元素的優(yōu)先級隊列，然后重復(fù)調(diào)用刪除最小元素的操作將它們按順序刪除。
堆排序分為兩個階段。構(gòu)造階段中，將原始數(shù)組重新組織安排進(jìn)一個堆中；然后在下沉排序階段，從堆中按遞減順序取出所有元素并得到排序結(jié)果。
為了排序需要，不再將優(yōu)先級隊列的具體表示隱藏，將直接使用swim和sink操作。這樣在排序時就可以將需要排序的數(shù)組本身作為堆，因此無需任何額外空間。
/**
 * 堆排序
 */
public class HeapSort {
    public static void sort(Comparable[] a){
        int n = a.length - 1; // index=0的位置不使用, n是最后一個index
        buildHeap(a, n);
        while(n>1){
            exchange(a,1,n--);
            sink(a,1,n);
        }
    }
    /**
     * 構(gòu)造堆
     */
    private static void buildHeap(Comparable[] a, int n) {
        for(int k = n/2; k>=1; k--)    
            sink(a, k, n);
    }

    private static void exchange(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    private static void sink(Comparable[] a, int k, int n) {
        while(2*k <= n){
            int j = 2*k;
            if(j
結(jié)果：
[ , a, e, e, l, m, o, p, r, s, t, x]


該算法用sink方法將a[1]到a[n]的元素排序(n=len-1),sink接受的參數(shù)需要修改。

for循環(huán)構(gòu)造堆，while循環(huán)將最大元素a[1]和a[n]交換并修復(fù)堆，如此重復(fù)直到堆變?yōu)榭?/p>
調(diào)用exchange時索引減一即可



下圖是堆的構(gòu)造和下沉過程：

堆排序的主要工作是在第二階段完成的。

刪除堆中最大元素

放入堆縮小后數(shù)組空出的位置。

進(jìn)行下沉操作。
命題R：用下沉操作由N個元素構(gòu)造堆 只需要少于2N次比較以及少于N次交換。


命題S：將N個元素排序，堆排序只需要少于（2NlgN+2N）次比較（以及一半次數(shù)的交換）。
第一次for循環(huán)構(gòu)造堆，第二次while循環(huán)在下沉排序中銷毀堆。都是基于sink方法。
將該實現(xiàn)和優(yōu)先級隊列的API獨立開是為了突出這個排序算法的簡潔性，構(gòu)造和sink分別只需幾行代碼。
堆排序在排序復(fù)雜性的研究中有很重要的地位，是所知的唯一能夠同時最優(yōu)的利用空間和時間的方法。
最壞情況也能保證2NlgN次比較和恒定的額外空間?？臻g緊張時很流行。
但是現(xiàn)代系統(tǒng)許多應(yīng)用很少使用它，因為它無法利用緩存。數(shù)組元素很少和相鄰元素進(jìn)行比較，因此緩存Miss遠(yuǎn)遠(yuǎn)高于大多數(shù)比較都在相鄰元素之間進(jìn)行的算法。


上面的幾種排序方法都是基于比較排序的算法。時間復(fù)雜度下界是O(nlogn)
下面介紹的三種排序是非基于比較的算法。計數(shù)排序，桶排序，基數(shù)排序。是可以突破O(nlogn)的下界的。
但是非基于比較的排序算法使用限制比較多。

計數(shù)排序進(jìn)對較小整數(shù)進(jìn)行排序，且要求排序的數(shù)據(jù)規(guī)模不能過大

基數(shù)排序可以對長整數(shù)進(jìn)行排序，但是不適用于浮點數(shù)。

桶排序可以對浮點數(shù)進(jìn)行排序
下面一一來學(xué)習(xí)。


7.計數(shù)排序
在排序的時候就知道其位置，那么就掃描一遍放入正確位置。如此以來，只需知道有多大范圍就可以了。這就是計數(shù)排序的思想。
性能：時間復(fù)雜度O(n+k)，線性時間，并且穩(wěn)定！
優(yōu)點：不需比較，利用地址偏移，對范圍固定在[0,k]的整數(shù)排序的最佳選擇。是排序字符串最快的排序算法
缺點：用來計數(shù)的數(shù)組的長度取決于帶排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值和最小值的差加1），這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和空間。
/**
 * 計數(shù)排序
 */
public class CountSort {
    public static int[] sort(int[] array){
        int[] result = new int[array.length];    // 存儲結(jié)果
        int max = max(array);                // 找到待排序數(shù)組中的最大值max
        int[] temp = new int[max+1];         // 申請一個大小為max+1的輔助數(shù)組
        for(int i = 0; i=0; i--){
            int v = array[i];            // 當(dāng)前元素
            result[temp[v] - 1] = v;    // 當(dāng)前元素作為索引，得到輔助數(shù)組元素，減一后的結(jié)果作為result中的索引，該處放置當(dāng)前的遍歷元素
            temp[v] = temp[v] - 1;        // 輔助數(shù)組相應(yīng)位置減少1，以供下個相同元素索引到正確位置
        }
        return result;
    }
    private static int max(int[] array) {
        int max = array[0];
        for(int i = 1; i < array.length; i++)
            if(array[i] > max)    max = array[i];
        return max;
    }
    public static void main(String[] args) {
        int[] arr = {3,4,1,7,2,8,0};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }
}
http://zh.visualgo.net/sorting
如果手動比較難以理解，可參照以上鏈接的可視化過程來觀察。
擴展：設(shè)計算法，對于給定的介于0--k之間的n個整數(shù)進(jìn)行預(yù)處理，并在O(1)時間內(nèi)得到這n個整數(shù)有多少落在了(a,b]區(qū)間內(nèi)。以上算法即可用來處理，預(yù)處理的時間為O(n+k)。

用計數(shù)排序中的預(yù)處理方法，預(yù)處理輔助數(shù)組，使得temp[i]為不大于i的元素的個數(shù)。

(a,b]區(qū)間內(nèi)元素個數(shù)即為temp[b] - temp[a]


/**
 * 計數(shù)排序的擴展
 */
public class CountSortExt {
    private int[] temp;        // 輔助數(shù)組
    public CountSortExt(int[] a){
        int max = max(a);
        temp = new int[max+1];
        for(int i = 0; i
結(jié)果為：
5

8.桶排序
參考http://www.growingwiththeweb....
使用場景：輸入的待排序數(shù)組在一個范圍內(nèi)均勻分布。
復(fù)雜度：

什么時候是最好情況呢？

O(n+k)的額外空間不是個事兒。

上面說到的使用場景：輸入數(shù)組在一個范圍內(nèi)均勻分布。
那么什么時候是最壞呢？

數(shù)組的所有元素都進(jìn)入同一個桶。


/**
 * 桶排序
 */
public class BucketSort {
    private static final int DEFAULT_BUCKET_SIZE = 5;
    public static void sort(Integer[] array){
        sort(array, DEFAULT_BUCKET_SIZE);
    }
    public static void sort(Integer[] array, int size) {
        if(array == null || array.length == 0)    return;
        // 找最大最小值
        int min = array[0], max = array[0];
        for(int i=1; i max)    max = array[i];
        }
        
        // 初始化桶
        int bucketCount = (max - min) / size + 1;
        List> buckets = new ArrayList<>(bucketCount);
        for(int i = 0; i < bucketCount; i++)
            buckets.add(new ArrayList());
        
        // 把輸入數(shù)組均勻分布進(jìn)buckets
        for(int i = 0; i currentBucket = buckets.get(i);
            Integer[] bucketArray = new Integer[currentBucket.size()];
            bucketArray = currentBucket.toArray(bucketArray);
            Arrays.sort(bucketArray);
            for(int j = 0; j< bucketArray.length; j++)
                array[currentIndex++] = bucketArray[j];
        }
    }
    public static void main(String[] args) {
        Integer[] array = {3,213,3,4,5,32,3,88,10};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}
[3, 3, 3, 4, 5, 10, 32, 88, 213]



9.基數(shù)排序
非比較型整數(shù)排序算法，原理是將整數(shù)按位切割成不同數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能適用于整數(shù)。
實現(xiàn)：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零，然后從最低位開始，依次進(jìn)行一次排序，這樣從最低位排序一直到最高位排序完成后，數(shù)列就變成有序的。
實現(xiàn)參考鏈接：
http://www.growingwiththeweb....
該基數(shù)排序基于LSD(Least significant digit)，從最低有效關(guān)鍵字開始排序。首先對所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對所有的數(shù)據(jù)按照首要關(guān)鍵字排序。

/**
 * 基數(shù)排序
 */
public class RadixSort {
    public static void sort(Integer[] array){
        sort(array, 10);
    }

    private static void sort(Integer[] array, int radix) {
        if(array == null || array.length == 0)    return;
        // 找最大最小值
        int min = array[0], max = array[0];
        for(int i = 1; i max)    max = array[i];
        }
        
        
        int exponent = 1;
        int off = max - min;
        // 對每一位進(jìn)行計數(shù)排序
        while(off / exponent >= 1){
            countingSortByDigit(array, radix, exponent, min);
            exponent *= radix;
        }
    }

    private static void countingSortByDigit(Integer[] array, int radix, int exponent, int min) {
        int bucketIndex;
        int[] buckets = new int[radix];
        int[] output = new int[array.length];
        // 初始化桶
        for(int i=0; i=0; i--){
            bucketIndex = (int)(((array[i] - min) / exponent) % radix);
            output[--buckets[bucketIndex]] = array[i];
        }
        // 拷貝回去
        for(int i =0; i
先總結(jié)到這里。