摘要：計數(shù)排序之前接觸的選擇快排等算法，都是著眼于怎么更快的調(diào)整元素位置，以達(dá)到排序的目的。桶排序桶排序能解決浮點(diǎn)數(shù)字的問題，至于槽大嘛，依然深受其害。思路桶排序與計數(shù)排序的思路多少有些類似，有數(shù)組整裝待排，還是一如既往的從小到大好了。

之前接觸的選擇、快排等算法，都是著眼于“怎么更快的調(diào)整元素位置”，以達(dá)到排序的目的。而計數(shù)排序則不然，設(shè)計思路可謂另辟蹊徑！

我們對15個10以內(nèi)（0-10）的數(shù)字按從小到大的順序進(jìn)行排序，比如source = [6, 8, 6, 2, 2, 10, 8, 5, 1, 9, 6, 4, 0, 2, 7]，計數(shù)排序是這么運(yùn)作的。

構(gòu)建計數(shù)槽——一個索引（可視作編號）從0到10的int數(shù)組，數(shù)組中的元素都初始為0

遍歷源數(shù)組source，以計數(shù)

既然叫計數(shù)槽（叫計數(shù)器也成，我更習(xí)慣把數(shù)組型的結(jié)構(gòu)稱之為“槽”），自然是計數(shù)用的。

1.遍歷源數(shù)組，首先拿到第一個“元素 6”，將其放入對應(yīng)的編號為 6 的槽。注意，這里不是將元素本身放入，只是進(jìn)行計數(shù)！將“槽 6”的數(shù)字計為1，表示元素6已經(jīng)有1個了。

2.繼續(xù)遍歷，第二個元素 8，放入編號為 8 的槽；第三個元素，值依然是6，計數(shù)再次+1后6號槽的數(shù)字變?yōu)?（表示元素6已經(jīng)有2個了）……

遍歷全部數(shù)字完成計數(shù)，其實翻譯成文字就是source = [6, 8, 6, 2, 2, 10, 8, 5, 1, 9, 6, 4, 0, 2, 7]數(shù)組中，有1個“元素0”，1個“元素1”，3個“元素2”，0個“元素3”,1個“元素4”，1個“元素5”，3個“元素6”，1個“元素7”，2個“元素8”，1個“元素9”，1個“元素10”。

出槽：按指定順序（從小到大）列出數(shù)字

可以看到，圖中的虛線框中的數(shù)字已經(jīng)是最終結(jié)果了！

按照上述思路編寫代碼：

import com.google.common.collect.Lists;

import java.util.LinkedList;
import java.util.Random;

/**
 * @description: 計數(shù)排序
 * @author: liuzijian
 * @date: 2018-04-17 08:29
 */
public class CounterOrder {
    int counterArr[] = new int[11]; //計數(shù)槽

    LinkedList fifeenNum = Lists.newLinkedList();

    /**
     * 隨機(jī)數(shù)初始化0-10的15個數(shù)字
     */
    private void init(){
        Random random = new Random();
        for(int i=0;i<15;i++){
            fifeenNum.add(random.nextInt(11));
        }
        System.out.println("source="+fifeenNum);
    }

    public CounterOrder(){
        init();
    }

    /**
     * 計數(shù)排序
     */
    public LinkedList doOrder(){
        //  <<<<<<<<<   1.計數(shù)
        for(int i:fifeenNum){
            int count = counterArr[i];
            count++;
            counterArr[i] = count;
        }

        // <<<<<<<<<   2.出槽
        LinkedList resList = Lists.newLinkedList();
        for(int i=0,len=counterArr.length;i0){
                resList.add(i);
                count--;
            }
        }
        return resList;
    }

    public static void main(String[] args) {
        CounterOrder counter = new CounterOrder();
        System.out.println("result is "+counter.doOrder());
    }
}

其實，這個demo可以說是計數(shù)排序的低配閹割版，雄壯健全版比這稍復(fù)雜些。容老夫賣個關(guān)子，桶排序部分會解釋這里。

先拋出一個問題，供大家思考：如果待排序的數(shù)字中存在負(fù)數(shù)，怎么處理？這個問題不難，比如對-10到10的數(shù)字進(jìn)行排序，完全可以構(gòu)建個“21位的計數(shù)槽”，不過每個槽負(fù)責(zé)計數(shù)的元素變成了“索引-10”，即槽0對應(yīng)-10的計數(shù)，槽1對應(yīng)-9的計數(shù)……以此類推，并且出槽的時候記得+10就是了！

計數(shù)排序真正的問題，或者說弊端有兩個：

不擅長處理范圍跨度很大的數(shù)字排序

這點(diǎn)很好理解，比如范圍在-20000到20000，僅僅選10個數(shù)字（比如：{-20000,-726...,20000,826...}）進(jìn)行排序，槽需要很大的說。

浮點(diǎn)型數(shù)字不好處理

浮點(diǎn)怎么處理？對于兩位小數(shù)的浮點(diǎn)，可采用“先乘100后續(xù)再除100”的方式曲線救國，但這樣很容易產(chǎn)生上面“槽大”的問題，比如小數(shù)位數(shù)多（試想2位整數(shù)4位小數(shù)的情況——31.4159）。

桶排序能解決浮點(diǎn)數(shù)字的問題，至于“槽大”嘛，依然深受其害。

桶排序與計數(shù)排序的思路多少有些類似，有數(shù)組[67, 29, 74, 52, 13, 16, 15, 59, 20, 61, 43, 38]整裝待排，還是一如既往的從小到大好了。

桶劃分：設(shè)定桶的元素范圍（姑且定為 10），進(jìn)行第一次遍歷，以獲取最大值、最小值和桶的個數(shù)

計數(shù)排序的代碼demo，稱其為低配閹割版的原因也在于此——我們硬性規(guī)定了0-10的槽。如果我們通過1次遍歷，獲取到最小值和最大值，假如min=3 max=6，那么是不是只用四個槽就能實現(xiàn)計數(shù)了？

入桶：依次將元素放入適合自己的桶中（按桶設(shè)定的數(shù)字范圍）

線通過顏色、虛實等作區(qū)分了，但還是有些亂 - -！

總之，最后桶中的元素分布如下。

桶內(nèi)排序

各個桶之間的元素已經(jīng)排好序了（桶0的元素 < 桶1的元素），但是桶內(nèi)的元素順序依然混亂，比如桶3中的 52 43，接下來需要對每個桶中的元素進(jìn)行排序。桶內(nèi)元素的排序方式方法不限，快排、選擇等等看心情……

示例中只有桶1和桶3需要排序（其實是每個桶都要做桶內(nèi)排序，桶內(nèi)排序的時機(jī)可以選擇在“入桶”或“出桶”時）

元素出桶

沒啥好說的，順序拿出就好。

桶排序代碼如下：

import com.google.common.collect.Lists;

import java.util.LinkedList;

/**
 * @description: 桶排序
 * @author: liuzijian
 * @date: 2018-04-18 14:06
 */
public class BucketSort {
    int arr[] = {67, 29, 74, 52, 13, 16, 15, 59, 20, 61, 43, 38};   //待排序數(shù)組

    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort();
        LinkedList res = bucketSort.doOrder();
        System.out.println(res);
    }

    /**
     * @description: 桶排序
     * @return: java.util.LinkedList
     * @date: 2018/4/20 16:22
     */
    public LinkedList doOrder() {
        InitParam initParam = firstLoop();  //首次遍歷，獲取最大值、最小值、桶個數(shù)等信息

        LinkedList[] bucket = new LinkedList[initParam.bucketNum]; //桶初始化

        // <<<<<<<  入桶方法 >>>>>>>
        for(int i:arr){
            int bucketIndex = (i-initParam.min)/elementNum; //計算元素歸屬于哪個桶
            LinkedList list = bucket[bucketIndex];
            if(list==null){
                list = new LinkedList<>();
                bucket[bucketIndex] = list;
            }

            //入桶的同時進(jìn)行桶內(nèi)排序
            addBySort(i,list);
        }

        // <<<<<<<  出桶方法 >>>>>>>
        LinkedList resList = Lists.newLinkedList();
        for(LinkedList bucketElement:bucket){
            if(bucketElement!=null && bucketElement.size()>0){
                resList.addAll(bucketElement);
            }
        }
        return resList;
    }

    /**
     * 按從小到大的順序進(jìn)行插入
     * @param i
     * @param list
     */
    private void addBySort(int i,LinkedList list){
        if(list.size()==0){
            list.add(i);
            return;
        }

        int index = 0;

        for(Integer ele:list){
            if(i>=ele){
                index++;
            }else{
                break;
            }
        }
        list.add(index,i);
    }

    final int elementNum = 10;

    /**
     * 封裝參數(shù)
     */
    class InitParam {
        int min;    //最小值
        int max;    //最大值
        int bucketNum;  //桶個數(shù)

        public InitParam(int min, int max, int bucketNum) {
            this.min = min;
            this.max = max;
            this.bucketNum = bucketNum;
        }
    }

    /**
     * @description: 第一次輪詢，獲取最大值、最小值和桶個數(shù)
     * @return: void
     * @date: 2018/4/18 14:18
     */
    public InitParam firstLoop() {
        int min = arr[0];
        int max = arr[0];
        for (int i : arr) {
            if (i < min) {
                min = i;
            }
            if (i > max) {
                max = i;
            }
        }
        int addition = (max - min) % elementNum == 0 ? 0 : 1;   //如果有余數(shù)，桶個數(shù)+1
        int bucketNum = (max - min) / elementNum + addition;

        return new InitParam(min, max, bucketNum);
    }
}

桶排序的關(guān)鍵在于桶劃分和桶內(nèi)排序算法的選擇。

時間角度

每個桶負(fù)責(zé)的元素范圍大，則桶的個數(shù)少；每個桶負(fù)責(zé)的元素范圍小，則桶的個數(shù)多。打個比方，對范圍在0-20000之間的數(shù)字進(jìn)行排序，如果桶元素范圍設(shè)置為10，則需要2000個桶；如果桶范圍選擇2000，則只需要10個桶。而不同的桶內(nèi)排序算法，隨著待排元素個數(shù)的增加，表現(xiàn)出的耗時增長幅度，也不盡相同。

空間角度

桶排序一種是比較耗空間的算法，尤其是我現(xiàn)在的這種實現(xiàn)方式——第一次遍歷時，計算好了桶的個數(shù)，進(jìn)而劃分好桶。還以范圍在0-20000的數(shù)字排序為例，如果只有5個數(shù)source={20000,371,372,370,0}(當(dāng)然這么少的數(shù)字可能就直接選其它排序方式了)，依然保持每個桶的負(fù)責(zé)范圍10，一次性初始化好的2000個桶，最后只會用到3個桶，剩下的1997個空桶的唯一作用就是浪費(fèi)空間！那么是不是可以每拿到一個元素，算出它的桶編號后，在入桶時僅僅初始化這一個桶呢？這樣對于上面的source數(shù)組，我最終只需要構(gòu)建桶0、桶370和桶2000共3個桶！

去掉了入桶時的順序插入方法，改為出桶時先計數(shù)排序再出桶。
直接上代碼吧：

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @description: 桶排序空間優(yōu)化版
 * @author: liuzijian
 * @date: 2018-04-18 14:06
 */
public class BucketSortUpgrade {
    int arr[] = {306, 20000, 304, 12, 768, 310, 303, 307};   //待排序數(shù)組
    final int elementNum = 10;
    int min;    //最小值
    int max;    //最大值
    int bucketNum;  //桶個數(shù)

    public static void main(String[] args) {
        BucketSortUpgrade bucketSort = new BucketSortUpgrade();
        LinkedList res = bucketSort.doOrder();
        System.out.println(res);
    }

    /**
     * @description: 桶排序
     * @return: java.util.LinkedList
     * @date: 2018/4/20 16:22
     */
    public LinkedList doOrder() {
        firstLoop();  //首次遍歷，獲取最大值、最小值、桶個數(shù)等信息

        Map> bucket = Maps.newTreeMap();

        // <<<<<<<  入桶方法 >>>>>>>
        for (int i : arr) {
            int bucketIndex = (i - min) / elementNum; //計算元素歸屬于哪個桶
            LinkedList list = bucket.get(bucketIndex);
            if (list == null) {
                list = new LinkedList<>();
                bucket.put(bucketIndex, list);
            }
            list.add(i);
        }

        // <<<<<<<  出桶方法 >>>>>>>
        LinkedList resList = Lists.newLinkedList();
        Iterator>> iterator = bucket.entrySet().iterator();
        int[] counter = new int[elementNum];    //計數(shù)器提到外面來，避免每次都重新分配計數(shù)器所需空間
        while (iterator.hasNext()) {
            Map.Entry> element = iterator.next();
            if (element.getValue() != null && element.getValue().size() > 0) {
                resList.addAll(outBucket(element,counter));   //計數(shù)排序方式出桶
                iterator.remove();  //每個桶完成出桶操作后，就釋放桶空間
            }
        }
        return resList;
    }

    /**
     * 計數(shù)排序方式出桶
     *
     * @param bucketElement
     * @return
     */
    private List outBucket(Map.Entry> bucketElement,int[] counter) {
        Integer bucketNo = bucketElement.getKey();
        int bucketStart = bucketNo * elementNum + min;

        for(int i=0;i resList = Lists.newLinkedList();
        for (int i = 0; i < elementNum; i++) {
            int count = counter[i];
            if (count > 0) {
                resList.add(bucketStart + i);
                count--;
            }
        }
        return resList;
    }


    /**
     * @description: 第一次輪詢，獲取最大值、最小值和桶個數(shù)
     * @author: liuzijian
     * @return: void
     * @date: 2018/4/18 14:18
     */
    public void firstLoop() {
        min = arr[0];
        max = arr[0];
        for (int i : arr) {
            if (i < min) {
                min = i;
            }
            if (i > max) {
                max = i;
            }
        }
        int addition = (max - min) % elementNum == 0 ? 0 : 1;   //如果有余數(shù)，桶個數(shù)+1
        bucketNum = (max - min) / elementNum + addition;
    }
}