數(shù)據(jù)結(jié)構(gòu)與算法-算法篇：排序—計數(shù)排序（八）

數(shù)據(jù)結(jié)構(gòu)與算法系列文章：數(shù)據(jù)結(jié)構(gòu)與算法目錄

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中势就。作為一種線性時間復雜度的排序泉瞻，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

計數(shù)排序的特征：
數(shù)組的元素都要是大于0的整數(shù)苞冯，計數(shù)排序不是比較排序袖牙，排序的速度快于任何比較排序算法。
由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1）舅锄，這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組鞭达，需要大量時間和內(nèi)存。
所以計數(shù)排序是用來排序1到100之間的數(shù)字的最好的算法皇忿。

#######圖解計數(shù)排序：
以[ 3畴蹭，5，8鳍烁，2叨襟，5，4 ]這組數(shù)字示例：
1幔荒、首先糊闽，我們找到這組數(shù)字中最大的數(shù)： 8，創(chuàng)建一個最大下標為 8 （數(shù)組中最大值+1）的空數(shù)組 arr 爹梁。

計數(shù)排序1.png

2右犹、遍歷數(shù)據(jù)，將數(shù)據(jù)的出現(xiàn)次數(shù)填入arr中對應的下標位置中姚垃。數(shù)組中的值為新創(chuàng)建數(shù)組的索引念链，對應內(nèi)容為該值出現(xiàn)的次數(shù)。

計數(shù)排序2.png

3积糯、遍歷 arr 钓账，將數(shù)據(jù)依次取出即可。

計數(shù)排序3.png

實現(xiàn)：

/// <summary>
/// 計數(shù)排序
/// </summary>
/// <param name="arr"></param>
public void CountingSort(int[] arr)
{
    // 找出數(shù)組中最大的
    int max = arr[0];
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }

    // 創(chuàng)建計數(shù)數(shù)組
    int[] countArr = new int[max + 1];

    // 開始計數(shù)
    for (int i = 0; i < arr.Length; i++)
    {
        countArr[arr[i]]++;
    }

    // 排序
    int sortedIndex = 0;
    for (int i = 0; i < countArr.Length; i++)
    {
        while (countArr[i] > 0)
        {
            arr[sortedIndex++] = i;
            countArr[i]--;
        }
    }
}

穩(wěn)定排序：

有一個需求就是當對成績進行排名次的時候絮宁，如何在原來排前面的人，排序后還是處于相同成績的人的前面服协。

解題的思路是對 countArr 計數(shù)數(shù)組進行一個變形绍昂，來和名次掛鉤，我們知道 countArr 存放的是分數(shù)的出現(xiàn)次數(shù)偿荷，那么其實我們可以算出每個分數(shù)的最大名次窘游，就是將 countArr 中的每個元素順序求和。

如下圖：

穩(wěn)定排序.png

變形意思：

我們把原數(shù)組[ 2跳纳，5忍饰，8，2寺庄，5艾蓝，4 ]中的數(shù)據(jù)依次拿來去 countArr 去找力崇，你會發(fā)現(xiàn) 3 這個數(shù)在 countArr[3] 中的值是 2 ，代表著排名第二名赢织，（因為第一名是最小的 2亮靴，對吧？）于置，5 這個數(shù)在 countArr[5] 中的值是 5 茧吊，為什么是 5 呢？我們來數(shù)數(shù)八毯，排序后的數(shù)組應該是[ 2搓侄，3，4话速，5讶踪，5，8 ]尿孔，5 的排名是第五名俊柔，那 4 的排名是第幾名呢？對應 countArr[4] 的值是 3 活合，第三名雏婶，5 的排名是第五名是因為 5 這個數(shù)有兩個，自然占據(jù)了第 4 名和第 5 名白指。

所以我們?nèi)∨琶臅r候應該特別注意留晚，原數(shù)組中的數(shù)據(jù)要從右往左取，從 countArr 取出排名后要把 countArr 中的排名減 1 告嘲，以便于再次取重復數(shù)據(jù)的時候排名往前一位错维。

實現(xiàn)：

/// <summary>
/// 計數(shù)排序
/// </summary>
/// <param name="arr"></param>
public void CountingSort(int[] arr)
{
    // 找出數(shù)組中最大的
    int max = arr[0];
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }

    // 創(chuàng)建計數(shù)數(shù)組
    int[] countArr = new int[max + 1];

    // 開始計數(shù)
    for (int i = 0; i < arr.Length; i++)
    {
        countArr[arr[i]]++;
    }

    //順序累加
    for (int i = 1; i < max + 1; ++i)
    {
        countArr[i] = countArr[i - 1] + countArr[i];
    }

    //排序后的數(shù)組
    int[] sortedArr = new int[arr.Length];

    //排序
    for (int i = arr.Length - 1; i >= 0; --i)
    {
        int value = arr[i];
        sortedArr[countArr[value] - 1] = value;
        countArr[value]--;
    }

    //將排序后的數(shù)據(jù)拷貝到原數(shù)組
    for (int i = 0; i < arr.Length; ++i)
    {
        arr[i] = sortedArr[i];
    }
}

計數(shù)局限性:

計數(shù)排序?qū)?shù)據(jù)范圍偏差比較大的，比如數(shù)組 1橄唬，9999 ]赋焕，則會比較耗時；
如果是[ 9998仰楚，9999 ]這種雖然值大但是相差范圍不大的數(shù)據(jù)我們可以使用偏移量解決隆判，比如這兩個數(shù)據(jù)，減掉 9997 后只需要申請一個 int[3] 的數(shù)組就可以進行計數(shù)僧界。

所以侨嘀，計數(shù)排序只適用于正整數(shù)并且取值范圍相差不大的數(shù)組排序使用，如1到100之間捂襟，它的排序的速度是非骋螅可觀的。