初始計數(shù)排序

摘自漫畫算法：

計數(shù)排序是一種不基于元素比較盗痒，利用數(shù)組索引來確定元素的正確位置的钩杰。

假設(shè)數(shù)組中有20個隨機整數(shù)，取值范圍0~10苛萎，要求用最快的速度把這20個整數(shù)從小到大進行排序桨昙。

如何給這些無序的隨機整數(shù)進行排序呢？

考慮到這些整數(shù)只能夠在0腌歉、1蛙酪、2乖菱、3咪惠、4、5凉逛、6馍驯、7阁危、8、9汰瘫、10這11個數(shù)中取值狂打，取值范圍有限。所以混弥，可以根據(jù)這有限的范圍趴乡，建立一個長度為11的數(shù)組。數(shù)組索引從0到10，元素初始值全為0浙宜。

計數(shù)排序1.png

假設(shè)20個隨機整數(shù)的值如下所示：

9官辽、3、5粟瞬、4同仆、9、1裙品、2俗批、7、8市怎、1岁忘、3、6区匠、5干像、3、4驰弄、0麻汰、10、9戚篙、7五鲫、9

下面就開始遍歷這個無序的隨機數(shù)列，每一個整數(shù)按照其值對號入座岔擂，同時位喂，對應(yīng)數(shù)組索引的元素進行加1操作。

例如第1個整數(shù)是9乱灵，那么數(shù)組索引為9的元素加1塑崖。

計數(shù)排序2.png

第2個整數(shù)是3，那么數(shù)組索引為3的元素加1痛倚。

計數(shù)排序3.png

以此類推规婆。最終，當數(shù)列遍歷完畢時状原，數(shù)組的狀態(tài)如下：

計數(shù)排序4.png

該數(shù)組中每一個索引位置的值代表數(shù)列中對應(yīng)整數(shù)出現(xiàn)的次數(shù)。

有了這個統(tǒng)計結(jié)果苗踪，排序就很簡單了颠区。直接遍歷數(shù)組，輸出數(shù)組元素的索引值通铲，元素的值是幾毕莱，就輸出幾次。

0，1朋截，1蛹稍，2，3部服，3唆姐，3，4廓八，4奉芦，5，5剧蹂，6声功，7，7宠叼，8先巴，9，9冒冬，9伸蚯，9，10

顯然窄驹，現(xiàn)在輸出的數(shù)列已經(jīng)是有序的了朝卒。

注意：計數(shù)排序它適用于一定范圍內(nèi)的整數(shù)排序。在取值范圍不是很大的情況下乐埠，它的性能甚至快過那些時間復(fù)雜度為O(nlogn)的排序抗斤。

計數(shù)排序的實現(xiàn)

整體代碼

import java.util.Arrays;

/**
 * 描述：計數(shù)排序
 * <p>
 * Create By ZhangBiao
 * 2020/5/31
 */
public class CountSort {

    /**
     * 計數(shù)排序
     *
     * @param arr
     * @return
     */
    public static int[] countSort(int[] arr) {
        // 1、得到數(shù)列的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 2丈咐、根據(jù)數(shù)列最大值確定統(tǒng)計數(shù)組的長度
        int[] countArray = new int[max + 1];
        // 3瑞眼、遍歷數(shù)列，填充統(tǒng)計數(shù)組
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i]]++;
        }
        // 4棵逊、遍歷統(tǒng)計數(shù)組伤疙，輸出結(jié)果
        int index = 0;
        int[] sortedArray = new int[arr.length];
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                sortedArray[index++] = i;
            }
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10};
        int[] sortedArray = countSort(arr);
        System.out.println(Arrays.toString(sortedArray));
    }

}

這段代碼在開頭有一個步驟，就是求數(shù)列的最大整數(shù)值max辆影。后面創(chuàng)建的統(tǒng)計數(shù)組countArray徒像，長度是max+1，以此來保證數(shù)組的最后一個下標是max蛙讥。

計數(shù)排序的優(yōu)化

從實現(xiàn)功能的角度來看锯蛀，這段代碼可以實現(xiàn)整數(shù)的排序。但是這段代碼也存在一些問題次慢。

當以數(shù)列的最大值來決定統(tǒng)計數(shù)組的長度旁涤，其實并不嚴謹翔曲。例如下面的數(shù)列：

95、94劈愚、91瞳遍、98、99菌羽、90掠械、99、93算凿、91份蝴、92

在這個數(shù)列中最大值是99，但最小的整數(shù)是90氓轰。如果創(chuàng)建長度為100的數(shù)組婚夫，那么前面從0到89的空間位置就都浪費了！

怎么解決這個問題呢署鸡？

很簡單案糙，只要不再以輸入數(shù)列的最大值+1作為統(tǒng)計數(shù)組的長度，而是以數(shù)列最大值 - 最小值 + 1作為統(tǒng)計數(shù)組的長度即可靴庆。

同時时捌，數(shù)列的最小值作為一個偏移量，用于計算整數(shù)在統(tǒng)計數(shù)組中的索引炉抒。

以剛才的數(shù)列為例奢讨，統(tǒng)計出數(shù)組的長度為99 - 90 + 1 = 10，偏移量等于數(shù)列的最小值90焰薄。對于第1個整數(shù)95拿诸，對應(yīng)的統(tǒng)計數(shù)組索引時95 - 90 = 5。

如圖所示：

計數(shù)排序 — 優(yōu)化1.png

注意：以上確實對計數(shù)排序進行了優(yōu)化塞茅。此外亩码，樸素版的計數(shù)排序只是簡單地按照統(tǒng)計數(shù)組的索引輸出元素值，并沒有真正給原始數(shù)列進行排序野瘦。

如果只是單純地給整數(shù)排序描沟，這樣做并沒有問題。但如果在現(xiàn)實業(yè)務(wù)里鞭光，例如給學(xué)生的考試分數(shù)進行排序吏廉，遇到相同的分數(shù)就會分不清是誰。

什么意思呢惰许？讓我們看看下面的例子席覆。

給出一個學(xué)生成績表，要求按照成績從高到底進行排序啡省，如果成績相同娜睛，則遵循原表固有順序。

那么卦睹，當我們填充統(tǒng)計數(shù)組以后畦戒，只知道有兩個成績并列為95分的同學(xué)，卻不知道哪一個是小紅结序，哪一個是小綠障斋。

計數(shù)排序 — 優(yōu)化2.png

那么如何解決呢？在這種情況下徐鹤，需要稍微改變之前的邏輯垃环，在填充完統(tǒng)計數(shù)組以后，對統(tǒng)計數(shù)組做一下變形返敬。

仍然以剛才的學(xué)生成績?yōu)槔熳瑢⒅暗慕y(tǒng)計數(shù)組變形成下面的樣子。

計數(shù)排序 — 優(yōu)化3.png

這是如何變形的呢劲赠？其實就是從統(tǒng)計數(shù)組的第2個元素開始涛目，每一個元素都加上前面所有元素之和。

為什么要相加呢凛澎？初次接觸的讀者可能會覺得莫名其妙霹肝。

這樣相加的目的，是讓統(tǒng)計數(shù)組存儲的元素值塑煎，等于相應(yīng)整數(shù)的最終排序位置的序號沫换。例如索引是9的元素值為5，代表原始數(shù)列的整數(shù)9最铁，最終的排序在第5位讯赏。

接下來，創(chuàng)建輸出數(shù)組sortedArray炭晒，長度和輸入數(shù)列一致待逞。然后從后向前遍歷輸入數(shù)列。

第1步网严，遍歷成績表最后一行的小綠同學(xué)的成績识樱。

小綠的成績是95分，找到countArray索引是5的元素震束，值是4怜庸，代表小綠的成績排名位置在第4位。

同時垢村，給countArray索引是5的元素值減1割疾，從4變成3，代表下次再遇到95分的成績時嘉栓，最終排名是第3.

計數(shù)排序 — 優(yōu)化4.png

第2步宏榕，遍歷成績倒數(shù)第2行的小白同學(xué)的成績拓诸。

小白的成績是94分，找到countArray索引是4的元素麻昼，值是2奠支，代表小白的成績排名位置在第2位。

同時抚芦，給countArray索引是4的元素值減1倍谜，從2變成1，代表下次再遇到94分的成績時（實際上已經(jīng)遇不到了）叉抡，最終排名是1尔崔。

計數(shù)排序 — 優(yōu)化5.png

第3步，遍歷成績表倒數(shù)第2行的小紅同學(xué)的成績褥民。

小紅的成績是95分季春，找到countArray索引是5的元素，值是3（最初是4消返，減1變成了3）鹤盒，代表小紅的成績排名位置在第3位。同時侦副，給countArray索引是5的元素值減1侦锯，從3變成2，代表下次再遇到95分的成績時（實際上已經(jīng)遇不到了）秦驯，最終排名是第2尺碰。

計數(shù)排序 — 優(yōu)化6.png

這樣一來，同樣是95分的小紅和小綠就能夠清除地排出順序了译隘，也正因為此亲桥，優(yōu)化版本的計數(shù)排序?qū)儆诜€(wěn)定排序。

后面的遍歷過程以此類推固耘，這里就不再詳細描述了题篷。

整體實現(xiàn)代碼：

import java.util.Arrays;

/**
 * 描述：計數(shù)排序
 * <p>
 * Create By ZhangBiao
 * 2020/5/31
 */
public class CountSort {

    /**
     * 計數(shù)排序
     *
     * @param arr
     * @return
     */
    public static int[] countSort(int[] arr) {
        // 1、得到數(shù)列的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 2厅目、根據(jù)數(shù)列最大值確定統(tǒng)計數(shù)組的長度
        int[] countArray = new int[max + 1];
        // 3番枚、遍歷數(shù)列，填充統(tǒng)計數(shù)組
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i]]++;
        }
        // 4损敷、遍歷統(tǒng)計數(shù)組葫笼，輸出結(jié)果
        int index = 0;
        int[] sortedArray = new int[arr.length];
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                sortedArray[index++] = i;
            }
        }
        return sortedArray;
    }

    /**
     * 優(yōu)化后的計數(shù)排序
     *
     * @param arr
     * @return
     */
    public static int[] countSort2(int[] arr) {
        // 1、得到數(shù)列的最大值和最小值拗馒，并算出差值d
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        int d = max - min;
        // 2路星、創(chuàng)建統(tǒng)計數(shù)組并統(tǒng)計對應(yīng)元素的個數(shù)
        int[] countArray = new int[d + 1];
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i] - min]++;
        }
        // 3、統(tǒng)計數(shù)組做變形诱桂，后面的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
        // 4洋丐、倒序遍歷原始數(shù)列呈昔，從統(tǒng)計數(shù)組找到正確位置，輸出到結(jié)果數(shù)組
        int[] sortedArray = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArray[countArray[arr[i] - min] - 1] = arr[i];
            countArray[arr[i] - min]--;
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        int[] sortedArray = countSort2(arr);
        System.out.println(Arrays.toString(sortedArray));
    }

}

計數(shù)排序的局限性

1友绝、當數(shù)列最大和最小值差距過大時韩肝，并不適合用計數(shù)排序

例如給出20個隨機數(shù)，范圍在0到1億之間九榔，這時如果使用計數(shù)排序，需要創(chuàng)建長度為1億的數(shù)組涡相。不但嚴重浪費空間哲泊，而且時間復(fù)雜度也會隨之升高。

2催蝗、當數(shù)列元素不是整數(shù)時切威，也不適合用計數(shù)排序

如果數(shù)列中的元素都是小數(shù)，如25.213丙号，或0.00 000 001這樣的數(shù)字先朦，則無法創(chuàng)建對應(yīng)的統(tǒng)計數(shù)組。這樣顯然無法進行計數(shù)排序犬缨。

對于這些局限性喳魏，另一種線性時間排序算法做出了彌補，這種排序算法叫做桶排序怀薛。