摘要：一基數(shù)排序桶排序介紹來(lái)源百科基數(shù)排序?qū)儆诜峙涫脚判颍址Q桶子法或，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些桶中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為，其中為所采取的基數(shù)，而為堆數(shù)，在某些時(shí)候，基

來(lái)源360百科：

基數(shù)排序(radix sort)屬于"分配式排序"(distribution sort)，又稱"桶子法"(bucket sort)或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些"桶"中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

從上面的簡(jiǎn)單介紹，是并不了解基數(shù)排序是怎么弄的～基數(shù)排序不同與其他的7種排序，其他7種排序本質(zhì)上都是按照交換或者比較來(lái)進(jìn)行排序，但是基數(shù)排序并不是，它是按照分配，回收(分配到不同的位置上，然后回收)..不斷分配..回收來(lái)進(jìn)行排序，直到有序..

聽(tīng)上去好像很高大上，很難的樣子，其實(shí)不然。基數(shù)排序挺簡(jiǎn)單的，下面我就來(lái)看一下基數(shù)排序的流程....

我們有9個(gè)桶，將數(shù)組的數(shù)字按照數(shù)值分配桶中：

ps:圖片來(lái)源于網(wǎng)絡(luò)，侵刪

上面我們發(fā)現(xiàn)：如果將桶按順序進(jìn)行回收，那么我們的排序就完成了～

可是，一般我們的數(shù)組元素都不僅僅是個(gè)位數(shù)的數(shù)字的呀，那么高位數(shù)的數(shù)字又怎么弄呢？？比如：23,44,511,6234這些高位數(shù)..

其實(shí)也是一樣的：

第一趟桶排序將數(shù)字的個(gè)位數(shù)分配到桶子里面去，然后回收起來(lái)，此時(shí)數(shù)組元素的所有個(gè)位數(shù)都已經(jīng)排好順序了

第二趟桶排序?qū)?shù)字的十位數(shù)分別分配到桶子里面去，然后回收起來(lái)，此時(shí)數(shù)組元素的所有個(gè)位數(shù)和十位數(shù)都已經(jīng)排好順序了(如果沒(méi)有十位數(shù)、則補(bǔ)0)

第三趟桶排序?qū)?shù)字的百位數(shù)分別分配到桶子里面去，然后回收起來(lái)，此時(shí)數(shù)組元素的所有個(gè)位數(shù)和十位數(shù)和百位數(shù)都已經(jīng)排好順序了(如果沒(méi)有百位數(shù)、則補(bǔ)0)

..................................

直至全部數(shù)(個(gè)、十、百、千位...)排好順序，那么這個(gè)數(shù)組就是有序的了。

ps:圖片來(lái)源于網(wǎng)絡(luò)，侵刪

機(jī)智的同學(xué)可能就會(huì)發(fā)現(xiàn)了，關(guān)于這個(gè)桶我們可以用二維數(shù)組來(lái)進(jìn)行存放。

10個(gè)桶子就是10列，如果分配時(shí)有的數(shù)字相同的話，那么就弄成多行~

首先我們有以下這個(gè)數(shù)組：

   int[] arrays = {6,  4322, 432, 344, 55 };

現(xiàn)在我們有10個(gè)桶子，每個(gè)桶子下能裝載arrays.length個(gè)數(shù)字..

int[][] buckets = new int[arrays.length][10];

效果如下：

將數(shù)組的每個(gè)個(gè)位數(shù)進(jìn)行分配到不同的桶子上：

分配完之后，我們按照順序來(lái)進(jìn)行回收：得到的結(jié)果應(yīng)該是這樣子的：{4322,432,344,55,6}

將數(shù)組的每個(gè)十位數(shù)進(jìn)行分配到不同的桶子上(像6這樣的數(shù)，往前邊補(bǔ)0)：

于是我們可以得到這樣的排序：

分配完之后，我們按照順序來(lái)進(jìn)行回收：得到的結(jié)果應(yīng)該是這樣子的：{6,4322,432,344,55}

將數(shù)組的每個(gè)百位數(shù)進(jìn)行分配到不同的桶子上(像6、55這樣的數(shù)，往前邊補(bǔ)0)：

于是我們可以得到這樣的排序：

分配完之后，我們按照順序來(lái)進(jìn)行回收：得到的結(jié)果應(yīng)該是這樣子的：{6,55,4322,344,432}

將數(shù)組的每個(gè)百位數(shù)進(jìn)行分配到不同的桶子上(像6、55，344，432這樣的數(shù)，往前邊補(bǔ)0)：

于是我們可以得到這樣的排序：

分配完之后，我們按照順序來(lái)進(jìn)行回收：得到的結(jié)果應(yīng)該是這樣子的：{6,55,344,432,4322}

此時(shí)我們的數(shù)組就已經(jīng)可以排好序了~~~過(guò)程就是這樣子，其實(shí)不難就只有兩個(gè)步驟：

將數(shù)組的每一位放進(jìn)桶子里

回收

循環(huán)......

我們的基數(shù)排序是按照個(gè)、十、百、千位...來(lái)進(jìn)行存放的。前面的演示是已經(jīng)知道數(shù)組元素的數(shù)據(jù)的情況下來(lái)進(jìn)行存放，但是一般我們是不去理會(huì)數(shù)組內(nèi)元素的值的。那如果位數(shù)很多(萬(wàn)位)或者都是個(gè)位數(shù)，這個(gè)條件我們?cè)趺慈ヌ幚砟兀?/p>

我們可以這樣做：先求出數(shù)組最大的值，然后不斷/10，只要它能大于0，那么它的位數(shù)還有~：

這個(gè)我在前面寫遞歸的時(shí)候就有這個(gè)代碼了，我就直接搬去遞歸的代碼過(guò)來(lái)了，順便復(fù)習(xí)一哈吧：

當(dāng)然了，更好的是直接用for循環(huán)來(lái)找出來(lái)就行了(易讀性好一些)

    /**
     * 遞歸，找出數(shù)組最大的值
     * @param arrays 數(shù)組
     * @param L      左邊界，第一個(gè)數(shù)
     * @param R      右邊界，數(shù)組的長(zhǎng)度
     * @return
     */

    public static int findMax(int[] arrays, int L, int R) {

        //如果該數(shù)組只有一個(gè)數(shù)，那么最大的就是該數(shù)組第一個(gè)值了
        if (L == R) {
            return arrays[L];
        } else {

            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整體的最大值

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }

    public static void radixSort(int[] arrays) {

        int max = findMax(arrays, 0, arrays.length - 1);

        //需要遍歷的次數(shù)由數(shù)組最大值的位數(shù)來(lái)決定
        for (int i = 1; max / i > 0; i = i * 10) {

            int[][] buckets = new int[arrays.length][10];

            //獲取每一位數(shù)字(個(gè)、十、百、千位...分配到桶子里)
            for (int j = 0; j < arrays.length; j++) {

                int num = (arrays[j] / i) % 10;

                //將其放入桶子里
                buckets[j][num] = arrays[j];
            }

            //回收桶子里的元素
            int k = 0;

            //有10個(gè)桶子
            for (int j = 0; j < 10; j++) {
                //對(duì)每個(gè)桶子里的元素進(jìn)行回收
                for (int l = 0; l < arrays.length ; l++) {

                    //如果桶子里面有元素就回收(數(shù)據(jù)初始化會(huì)為0)
                    if (buckets[l][j] != 0) {
                        arrays[k++] = buckets[l][j];

                    }
                    
                }
                
            }

        }
    }

搞了一堆數(shù)測(cè)試了一哈：

基數(shù)排序(桶排序)要理解起來(lái)并不困難，不過(guò)值得注意的是：基數(shù)排序?qū)τ胸?fù)數(shù)和0的數(shù)列難以進(jìn)行排序

因此，往往有0和負(fù)數(shù)的數(shù)組一般我們都不用基數(shù)來(lái)進(jìn)行排序

基數(shù)排序的要點(diǎn)就兩個(gè)：

分配：按照元素的大小來(lái)放入不同的桶子里

回收：將桶子里的元素按桶子順序重新放到數(shù)組中

重復(fù).....兩個(gè)步驟

參考資料：

http://www.cnblogs.com/skywang12345/p/3603669.html

http://www.cnblogs.com/developerY/p/3172379.html

https://www.cnblogs.com/zengzhihua/p/4456753.html

https://www.cnblogs.com/jin-nuo/p/5293554.html

https://www.cnblogs.com/protected/p/6603536.html

https://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y