计数排序是桶排序的一种特例，原理上跟桶排序差不多，但是思路是另外一种比较巧妙的排序，也是借助桶的原理来进行排序
算法过程
我们还是以班级内考试，分数是 0~5 分为例，来进行计数排序的过程。
各位同学的成绩.png
因为成绩是0~5分，我们依然准备6个“桶”来装，但这次并不是用桶来装成绩，而是来装考了这个成绩的学生有几个，我们就可以得到一个统计分数数量的 计数数组 ：
得到计数数组.png
得到 计数数组 之后，我们真正使用的并不是这个分数计数数组，而是将它改版，变成分数 计数累加数组 ，这个数组是通过依次累加计数数组而得到的。这个数组的意义在于，它表示比 自己小包括自己 的成绩一共有多少：
计数数组变为计数累加数组.png
从图中我们可以看到，最终得到的计数累加数组所表示的信息，比如：取得 0分或者比0分少 的人又1人，取得 3分或者比3分少 的人有7人。
接下来这个过程比较关键，我们依次的从最开始的所有人的成绩数组中 从后向前（否则排序就不稳定） 取出成绩，利用计数累加数组找到这个成绩在最终排序完毕的数组中的位置，然后将成绩插入这个最终排序完毕的数组，所有成绩都插入之后，最终排序完全的数组也就从没有元素到填满了所有的成绩元素。所有成绩都被按顺序的排列完毕！
根据计数累加数组将最初成绩数组排序过程.png
这就是计数排序的整个过程，计数排序是利用 计数数组 得到 计数累加数组，然后通过计数累加数组将原始成绩按顺序排列完毕的。
算法实现
#coding:utf-8
import numpy as np
# min: 数列中的最小值 ； max：数列中的最大值 ，便于计算
def counting_sort(data, min, max):
# 计数数组，并把所有的数量初始化为0
count_array = np.zeros(max - min + 1, np.int32)
# 统计所有元素的数量，并且写入数组的相应的位置
for number in data:
count_array[number] += 1
# 从前向后得到累加数量之后的数组
for i in range(1, len(count_array)):
count_array[i] += count_array[i-1]
# 从后向前依次拿到所有的数，对应的位置插入到新的数组中
sorted_data = np.empty(len(data), np.int32)
for i in range(len(data)-1, -1, -1):
sorted_data[count_array[data[i]] - 1] = data[i]
count_array[data[i]] -= 1
return sorted_data
data = np.random.randint(0, 20, 20)
print("排序之前的数据:{}".format(data))
sorted_data = counting_sort(data, 0, 19) # 所有的数中，最大的是19，最小的是0
print("排序后的数据:{}".format(sorted_data))
结果是：
计数排序的结果.png
上一篇：写给媳妇儿的算法（八）——桶排序
下一篇：写写给媳妇儿的算法（十）——斐波那切数列
