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

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

抽象出來(lái)的父類(lèi)為：

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

對(duì)應(yīng)的Java實(shí)現(xiàn)

/**
 1. 排序的抽象類(lèi)
 2.         可以接受任意類(lèi)型，可以自定義比較器
 3. @param 
 */
public abstract class Sort {
    /** 測(cè)試數(shù)組，這里為了方便使用整型數(shù)組*/
    protected static Integer[] testArray = { 3, 2, 5, 1, 4, 7 ,10};
    /** 繼承該類(lèi)需要實(shí)現(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;
    }
    /** 比較兩個(gè)元素的方法*/
    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));
    }
}

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

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

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

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

/**
 * 插入排序
 */
public class InsertSort extends Sort {
    @Override
    public void sort(Comparable[] array) {
        int len = array.length;
        // 把a(bǔ)[i] 插入到a[i-1], a[i-2], a[i-3]...中
        for (int i = 1; i < len; i++) {
            // j從i開(kā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

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

排序時(shí)間和輸入無(wú)關(guān)

最好和最壞都是一樣的

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

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

3.歸并排序

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

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

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

缺點(diǎn)：所需額外空間和N成正比。

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


3.1自頂向下的歸并排序算法
/**
* 歸并排序：自頂向下
*         分治思想的最經(jīng)典的一個(gè)例子。
*         這段遞歸代碼是歸納證明算法能夠正確地將數(shù)組排序的基礎(chǔ)：
*             如果它能將兩個(gè)子數(shù)組排序，它就能通過(guò)歸并兩個(gè)子數(shù)組來(lái)講整個(gè)數(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中，然后再歸并會(huì)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);
    }
}
對(duì)于16個(gè)元素的數(shù)組，其遞歸過(guò)程如下：

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

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

考慮2：測(cè)試數(shù)組是否已經(jīng)有序。可以添加一個(gè)判斷條件，如果array[ mid ] <= array[ mid + 1 ]就認(rèn)為數(shù)組已經(jīng)是有序的，并跳過(guò)merge方法，這個(gè)改動(dòng)不影響排序的遞歸調(diào)用，但是任意有序的子數(shù)組算法運(yùn)行的時(shí)間就變成線(xiàn)性了。

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



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

/**
 * 自底向上的歸并排序
 *         會(huì)多次遍歷整個(gè)數(shù)組，根據(jù)子數(shù)組大小進(jìn)行兩兩歸并。
 *         子數(shù)組的大小size初始值為1，每次加倍。
 *         最后一個(gè)子數(shù)組的大小只有在數(shù)組大小是size的偶數(shù)被時(shí)才會(huì)等于size，否則會(huì)比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個(gè)元素的數(shù)組，過(guò)程如下圖

4.冒泡排序
比較簡(jiǎn)單
/**
 * 冒泡排序
 * 時(shí)間：O(n^2)；空間O(1)
 * 穩(wěn)定，因?yàn)榇嬖趦蓛杀容^，不存在跳躍
 * 排序時(shí)間與輸入無(wú)關(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);
    }
}
缺陷：

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

當(dāng)排序的數(shù)據(jù)比較多時(shí)，排序的時(shí)間會(huì)明顯延長(zhǎng)，因?yàn)闀?huì)比較n*(n-1)/2次。



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

特點(diǎn)：原地排序（只需很小的一個(gè)輔助棧）；時(shí)間和NlgN成正比。同時(shí)具備這兩個(gè)優(yōu)點(diǎn)。
        另外，快排序的內(nèi)循環(huán)比大多數(shù)排序算法都短。
5.1 基本算法
快排序是一種分治的算法，將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，將兩部分獨(dú)立排序。
快排序和歸并排序互補(bǔ)：歸并排序?qū)?shù)組分成兩個(gè)子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個(gè)數(shù)組排序；
而快排序?qū)?shù)組排序的方式是當(dāng)兩個(gè)子數(shù)組都有序的時(shí)候，整個(gè)數(shù)組自然也就有序了。
第一種情況，遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之前；第二種情況，遞歸發(fā)生在處理整個(gè)數(shù)組之后。
歸并排序中，一個(gè)數(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;//左指針向右找到一個(gè)大于v的位置
            while(less(v, array[--j]))    if(j == low)    break;//右指針向左找到一個(gè)小于v的位置
            if(i >= j)    break;    // 如果左指針重疊或者超過(guò)右指針，跳出
            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相遇時(shí)主循環(huán)退出。在循環(huán)中，array[i]小于v時(shí)，增大i，a[j]大于v時(shí)，減小j，然后交換array[i]和array[j]來(lái)保證i左側(cè)的元素都不大于v，j右側(cè)的元素都不小于v。當(dāng)指針相遇時(shí)交換array[low]和array[j],切分結(jié)束，這樣切分值就留在array[j]中了。


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


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

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


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

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

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

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

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

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


6.1API的設(shè)計(jì)

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

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

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

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



看一個(gè)優(yōu)先級(jí)隊(duì)列的用例

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

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

當(dāng)一顆二叉樹(shù)的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子結(jié)點(diǎn)時(shí)，被稱(chēng)為堆有序。

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


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

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

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

在之前的排序中，通過(guò)輔助函數(shù)less和exchange函數(shù)來(lái)訪(fǎng)問(wèn)元素，但因?yàn)樗械脑囟荚跀?shù)組pq中，該實(shí)現(xiàn)為了更加緊湊，不再將數(shù)組作為參數(shù)傳遞。

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


比較和交換方法：

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

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

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

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

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

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

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


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

做到這一點(diǎn)的一種簡(jiǎn)單方法是給每個(gè)元素一個(gè)索引。

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



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

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

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

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

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



此處留坑，以后再看，這是庫(kù)中的源碼
/**
 * 索引優(yōu)先級(jí)隊(duì)列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)先級(jí)隊(duì)列用例：
多向歸并問(wèn)題：將多個(gè)有序的輸入流歸并成一個(gè)有序的輸入流。

輸入流可能來(lái)自多種一起的輸出（按時(shí)間排序），

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

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

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


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



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

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

刪除堆中最大元素

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

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


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


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

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

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

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


7.計(jì)數(shù)排序
在排序的時(shí)候就知道其位置，那么就掃描一遍放入正確位置。如此以來(lái)，只需知道有多大范圍就可以了。這就是計(jì)數(shù)排序的思想。
性能：時(shí)間復(fù)雜度O(n+k)，線(xiàn)性時(shí)間，并且穩(wěn)定！
優(yōu)點(diǎn)：不需比較，利用地址偏移，對(duì)范圍固定在[0,k]的整數(shù)排序的最佳選擇。是排序字符串最快的排序算法
缺點(diǎn)：用來(lái)計(jì)數(shù)的數(shù)組的長(zhǎng)度取決于帶排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值和最小值的差加1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和空間。
/**
 * 計(jì)數(shù)排序
 */
public class CountSort {
    public static int[] sort(int[] array){
        int[] result = new int[array.length];    // 存儲(chǔ)結(jié)果
        int max = max(array);                // 找到待排序數(shù)組中的最大值max
        int[] temp = new int[max+1];         // 申請(qǐng)一個(gè)大小為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，以供下個(gè)相同元素索引到正確位置
        }
        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
如果手動(dòng)比較難以理解，可參照以上鏈接的可視化過(guò)程來(lái)觀察。
擴(kuò)展：設(shè)計(jì)算法，對(duì)于給定的介于0--k之間的n個(gè)整數(shù)進(jìn)行預(yù)處理，并在O(1)時(shí)間內(nèi)得到這n個(gè)整數(shù)有多少落在了(a,b]區(qū)間內(nèi)。以上算法即可用來(lái)處理，預(yù)處理的時(shí)間為O(n+k)。

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

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


/**
 * 計(jì)數(shù)排序的擴(kuò)展
 */
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....
使用場(chǎng)景：輸入的待排序數(shù)組在一個(gè)范圍內(nèi)均勻分布。
復(fù)雜度：

什么時(shí)候是最好情況呢？

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

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

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


/**
 * 桶排序
 */
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ù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能適用于整數(shù)。
實(shí)現(xiàn)：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零，然后從最低位開(kāi)始，依次進(jìn)行一次排序，這樣從最低位排序一直到最高位排序完成后，數(shù)列就變成有序的。
實(shí)現(xiàn)參考鏈接：
http://www.growingwiththeweb....
該基數(shù)排序基于LSD(Least significant digit)，從最低有效關(guān)鍵字開(kāi)始排序。首先對(duì)所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對(duì)所有的數(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;
        // 對(duì)每一位進(jìn)行計(jì)數(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é)到這里。