計數(shù)排序是桶排序的一種特例例获，原理上跟桶排序差不多辽慕，但是思路是另外一種比較巧妙的排序蜡塌，也是借助桶的原理來進行排序
算法過程
我們還是以班級內(nèi)考試，分?jǐn)?shù)是 0~5 分為例适室，來進行計數(shù)排序的過程嫡意。
各位同學(xué)的成績.png
因為成績是0~5分，我們依然準(zhǔn)備6個“桶”來裝捣辆，但這次并不是用桶來裝成績蔬螟，而是來裝考了這個成績的學(xué)生有幾個，我們就可以得到一個統(tǒng)計分?jǐn)?shù)數(shù)量的 計數(shù)數(shù)組 ：
得到計數(shù)數(shù)組.png
得到 計數(shù)數(shù)組 之后汽畴，我們真正使用的并不是這個分?jǐn)?shù)計數(shù)數(shù)組旧巾，而是將它改版耸序，變成分?jǐn)?shù) 計數(shù)累加數(shù)組 ，這個數(shù)組是通過依次累加計數(shù)數(shù)組而得到的菠齿。這個數(shù)組的意義在于佑吝，它表示比 自己小包括自己 的成績一共有多少：
計數(shù)數(shù)組變?yōu)橛嫈?shù)累加數(shù)組.png
從圖中我們可以看到，最終得到的計數(shù)累加數(shù)組所表示的信息绳匀，比如：取得 0分或者比0分少 的人又1人芋忿，取得 3分或者比3分少 的人有7人。
接下來這個過程比較關(guān)鍵疾棵，我們依次的從最開始的所有人的成績數(shù)組中 從后向前（否則排序就不穩(wěn)定） 取出成績戈钢，利用計數(shù)累加數(shù)組找到這個成績在最終排序完畢的數(shù)組中的位置，然后將成績插入這個最終排序完畢的數(shù)組是尔，所有成績都插入之后殉了，最終排序完全的數(shù)組也就從沒有元素到填滿了所有的成績元素。所有成績都被按順序的排列完畢拟枚！
根據(jù)計數(shù)累加數(shù)組將最初成績數(shù)組排序過程.png
這就是計數(shù)排序的整個過程薪铜，計數(shù)排序是利用 計數(shù)數(shù)組 得到 計數(shù)累加數(shù)組，然后通過計數(shù)累加數(shù)組將原始成績按順序排列完畢的恩溅。
算法實現(xiàn)
#coding:utf-8
import numpy as np
# min: 數(shù)列中的最小值 隔箍； max：數(shù)列中的最大值 ，便于計算
def counting_sort(data, min, max):
# 計數(shù)數(shù)組脚乡，并把所有的數(shù)量初始化為0
count_array = np.zeros(max - min + 1, np.int32)
# 統(tǒng)計所有元素的數(shù)量蜒滩，并且寫入數(shù)組的相應(yīng)的位置
for number in data:
count_array[number] += 1
# 從前向后得到累加數(shù)量之后的數(shù)組
for i in range(1, len(count_array)):
count_array[i] += count_array[i-1]
# 從后向前依次拿到所有的數(shù)，對應(yīng)的位置插入到新的數(shù)組中
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("排序之前的數(shù)據(jù):{}".format(data))
sorted_data = counting_sort(data, 0, 19) # 所有的數(shù)中奶稠，最大的是19俯艰，最小的是0
print("排序后的數(shù)據(jù):{}".format(sorted_data))
結(jié)果是：
計數(shù)排序的結(jié)果.png
