详解计数排序算法原理与使用方法

算法概述

计数排序是一种非比较排序算法，用于将元素排列在特定顺序。计数排序可以用于整数和某些浮点数。它的基本思想是在需要排序的数组中，如果数组中的最小值是k，最大值是j，那么可以创建一个计数器数组来计算原始数组中每个数值的出现次数。依此可以遍历计数器数组并按计数器的计数值直接填充输出数组，从而生成排序后的数组。具体而言，计数排序由以下 3 个实质性部分组成：

1. 计数数组: 长度为需要排序的数字范围，遍历待排序序列，将序列中所有的数字按次数放入对应下标的计数数组。
2. 累加数组: 对计数数组进行逐个累和，可以得到每个数字应该排序的下标。
3. 排序数组: 根据累加数组，将待排序序列中的每个元素按顺序放入这个新的数组里。

算法流程

以整数一维数组排序为例，算法流程如下:

1. 扫描一遍序列找到最大值和最小值，取区间长度len=max-min+1，为计数数组的长度。
2. 定义计数数组c，一遍扫描序列，将出现的整数计数记录在相应的计数数组位置上，c[i]-=min，其中c[i]表示i出现的次数，i=min,max。
3. 接着扫描c数组，依次累加前面的值（累加后c[i]表示i在序列中排名的最大下标），从前向后将序列的数填充到r数组(注意取出时要加上min)上。
4. 此时r数组即为序列排序后的新序列。

具体代码如下:

void CountingSort(int* arr, int len)
{
    int min = arr[0], max = arr[0];
    for (int i = 1; i < len; i++)  // 找出区间上界和下界
    {
        if (arr[i] < min)
            min = arr[i];
        else if (arr[i] > max)
            max = arr[i];
    }

    int* c = new int[max - min + 1]();  // 计数器数组
    for (int i = 0; i < len; i++)
        c[arr[i] - min]++;  // 统计每个元素出现的次数
    for (int i = min + 1; i <= max; i++)
        c[i - min] += c[i - min - 1];  // 将计数器依次累加

    int* r = new int[len]();  // 结果数组
    for (int i = len - 1; i >= 0; i--)
    {
        r[c[arr[i] - min] - 1] = arr[i];  // 放置第 arr[i] 个元素
        c[arr[i] - min]--;  // 更新其对应于计数器的值
    }

    memmove(arr, r, len * sizeof(int));  // 将结果赋值回原数组中
    delete[] c;
    delete[] r;
}

算法示例

示例一

以序列a，b，c排序为例，不妨设序列为3，1，4，0，0，3，4，3。那么首先需要获取序列最小值、最大值、范围。可知最小值为0，最大值为4，范围就是[0, 4)，长度为5。

计数数组就是一个长度为5的数组，记录从0到4一共有多少个数字出现（出现个数即计数器值），第一个数字是零，存在的首位就改成0，第二个数字是一个，存在的首位就改成1，第三个数字是四，存在的首位就改成4，以此类推，数字0出现了两次，计数器中将0的数值设为了2，数字1出现了一次，计数器中将1的数值设为了1，数字2没有出现过，所以计数器中的2还是0，数字3出现了3次，计数器中将3的数值设为3，数字4出现了2次，计数器中将4的数值设为2。计数器数组为2，1，0，3，2。
累加数组就是一个长度为5的数组，记录每个值在排序后的序列中应该排在第几位。其实就是一个前缀和。首先将第一个数字计数累加到计数器的第0个数值里，再将第二个数字计数累加到计数器的第一个计数值里，接着是第三个数字，累加到计数器的第四个计数值里，以此类推，最后得到的数组就是0，2，3，6，8。
排序数组就是将原始数组按照累加数组的下标从后向前填值，得到的序列即是排序结束的序列。如果反过来，先放第一个“3”，一共出现3次，那么放到序列中就要从累加数组的最后一位往前放三个“3”，分别加上min，即放在第3位，第4位和第7位。接着放第二个数字0，一共出现了2次，同样也要从累加数组的最后面往前放两个数字0，放在第0位和第1位，以此类推。就得到了排序结果：0，0，1，3，3，3，4，4。

示例二

假设要给字符串进行排序，如“AACCBDEBBECEA”，可以将每个字符的ascii码进行计数排序：

按照字符出现的次数，可以得到计数器数组：

A的ascii码是65出现了2次
B的ascii码是66出现了3次
C的ascii码是67出现了2次
D的ascii码是68出现了1次
E的ascii码是69出现了2次

因为其中的字母序号是连续的，最小的是65，最大的是69，计数数组长度就是69-65+1=5

计数器数组就是长度为5的数组，记录从This is to inform you处于区间[65, 70)内的每一个数字出现次数（出现次数即为计数数组值）。这些数字是65、66、67、68、69，第65个数字出现了两次，计数数组中该数字下标的数值就是2, 第66个数字出现了三次，计数数组中该数字下标的数值就是3，以此类推。

累加数组同样是一个长度为5的数组，记录每个值在排序后的序列中应该排在第几位。计数数组累加后得到的数组为 2 5 7 8 10，比如最小的数字65，他在计数器中对应的下标是0，而且出现2次，因此累加数组的第一个数是2，同样，累加后的数组中的第二个数字是5，累加后的数组中的第一个数是2，所以累加后的数组中的第三个数字的值就是累加数组中的第二个元素加上计数数组中的第三个元素，即5+2=7，以此类推。

排序数组也是将原始数组按照累加数组的下标从后向前填值，即先从后往前扫描一遍计数器中的每个值，再根据该值在累加数组中得到该值在排序数组中的位置，放入该位置即可。

最终结果就是AACCEBBBDEECB。