查找与排序：计数排序
计数排序
计数排序有限制条件，序列里的元素必须是有限偏序集，如整数，如英文字母。那么它的性能为O(n+k)，其中n为元素个数，k为有限偏序集大小，如个位整数，k最大就是10，如英文字母，k最大就是26。
计数排序相当于利用偏序集的特点，对元素进行分组，分组数为偏序集的基数，举例子来说，一个长度为n的随机英文字母ABCDE序列，我们要排序，只需要将序列中的每个字母分组到自己那个组中，然后把组按次序串起来就行了，因为是偏序集，所以组之间本来就是有次序的。演示如下：
序列为S=”BAACCBEECCDDBA”，我们按照字母次序分组如下：
0 |
1 |
2 |
3 |
4 |
全部A字母 |
全部B字母 |
全部C字母 |
全部D字母 |
全部E字母 |
我们扫描序列S，把字母一个一个放到组中：
0 |
1 |
2 |
3 |
4 |
AAA |
BBB |
CCCC |
DD |
EE |
这样自然排好序了。
我们现在看程序的思路，我们用一个新的序列，将原序列中的字母放到正确的位置来。为了算出这个正确的位置，我们需要知道序列中每一个字母出现的次数。
我们从头到尾扫描串S，总共有14个字母，计一下数，得到如下字母次数数组：
0(A) |
1(B) |
2(C) |
3(D) |
4(E) |
3 |
3 |
4 |
2 |
2 |
然后我们根据次数数组，就能算出字母的输出位置，数组如下：
0(A) |
1(B) |
2(C) |
3(D) |
4(E) |
3 |
6 |
10 |
12 |
14 |
这个输出位置就是前一格的值加上自己这个字母的值，也就是截止位置。如对字母C来讲，前面两个字母占用了6个位置，本身C又有四个，所以C的截止位置为10。
接下来，我们从尾到头反过来扫描序列S：”BAACCBEECCDDBA”。首先碰到的字母为A，我们检查计数表，对应A的值为3，所以我们把它放在第3的位置：
A |
然后把计数表中对应的值减1，这样计数表成了：
0(A) |
1(B) |
2(C) |
3(D) |
4(E) |
2 |
6 |
10 |
12 |
14 |
下一次从序列中读取的字母为B，我们检查计数表，对应B的值为6，所以我们把它放在第6的位置。
A |
B |
然后把计数表中对应的值减1，这样计数表成了：
0(A) |
1(B) |
2(C) |
3(D) |
4(E) |
2 |
5 |
10 |
12 |
14 |
一直这么循环。
代码如下：
def CountingSort(S,BASE):
S0=['']*len(S) #return array
POS=[0]*len(BASE) #counting array
#counting
for c in S:
POS[ord(c)-ord('A')] += 1
#position
for i in range(1,len(POS)):
POS[i] += POS[i-1]
#generate new array
for i in range(len(S)-1,-1,-1): #desc order
idx=POS[ord(S[i])-ord('A')]-1
S0[idx]=S[i]
POS[ord(S[i])-ord('A')] -= 1
return S0
测试一下：
S=['B','A','A','C','C','B','E','E','C','C','D','D','B','A']
BASE=['A','B','C','D','E']
print(CountingSort(S,BASE))
运行结果：
['A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'C', 'D', 'D', 'E', 'E']
我们看到，计数排序只扫描了原序列2遍，还使用了一个长度更小的数组POS，所以整个排序性能为O(n)。
有的人爱动脑筋，觉得不需要在新序列中算位置，就用一个二维数组，第一维为ABCDE五个位置，第二维为序列S中的哪些对应的字母；甚至有人进一步想到了数组+链表结构。这样都是可以的，事实上，这种算法还有一种变形叫做桶排序，所谓桶就是你们想到的第一维数组，桶这个词太贴切了。
点击“阅读原文”,可进入原创书籍，阅读目录