8.计数排序
8.1 算法思想
计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），当o（k）< o（nlogn）时快于任何比较排序算法。这是一种 牺牲空间换取时间 的做法，而且当O(k)>O(n log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n log(n)), 如归并排序，堆排序）。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。
这种算法同时也有额外空间开销计数数组和结果数组，空间复杂度为o（n+k）
8.2 算法过程
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项； （由于这个原因，要排序的数必须在大于等于0，且由于时间复杂度的问题，数组元素的上限也有一定的限制，否则，时间复杂度不如比较类排序。）
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1.
8.2.1 算法举例
以下说明下计数排序的过程。以《算法导论》这本书的一个例子进行说明：
初始化数组： A[2,5,3,0,2,3,0,3]
假设我们已经事先知道A数组的最大值5，排序过程如下：
a）创建一个长度为6的临时存储数组空间C，并将C数组每一个元素初始化为0。
b）统计重复元素的个数。A数组的元素作为数组C的下标，扫描数组A，A数组元素每出现一次，数组C等于该元素的下标位置的元素加一。例如第一次扫描到的是2，则C[2]=0+1=1,…,第五次再次扫描到了2，C[2]=1+1=2，说明这个数组2的个数为2个。C[2,0,2,3,0,1]
c）计算有多少（y）个元素小于或等于数组C的下标。根据计数数组累加得到C[2,2,4,7,7,8] (小于等于0的有2个，小于等于1的有2个，小于等于2的4个，…小于等于5的有8个)
d）倒序扫描数组A的元素x，依次将元素放置于输出序列res[y]位置,y为小于或者等于这个元素的个数,同时临时数组C[x]=C[x]-1;重复这个过程直至扫描到数组A的首位元素。res[0,0,2,2,3,3,3,5]
因为倒叙遍历原数组，不会改变原来相等元素的相对位置，所以这是稳定的
简而言之就是先统计出数组A元素x小于或等于自身的元素个数y，将x放置于res[y]处，y-1，接着重复这个过程。
简而言之
以[5,3,6,6]数组为例，小于等于5的元素个数为2，小于等于3的元素个数为1，小于等于6的元素个数为4。res = [0,0,0,0]，从后往前遍历原数组，6，小于等于6的元素个数为4，最后一个6，放在res[4-1]的位置，这是在剩下的元素中，小于等于6的个数为4-1=3；在继续遍历，6，小于等于6的元素个数为3，放在res[3-1]的位置。再继续遍历，3，这时候小于等于3的元素个数为1，不变，放在res[1-1]的位置；5，小于等于5的元素个数为2，放在res[2-1]的位置。
8.3 python代码
def
countingSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
maxVal
=
max
(
numList
)
countArr
=
[
0
for
i
in
range
(
maxVal
+
1
)
]
for
i
in
numList
:
countArr
[
i
]
+=
1
for
i
in
range
(
1
,
len
(
countArr
)
)
:
countArr
[
i
]
+=
countArr
[
i
-
1
]
res
=
[
0
for
i
in
range
(
n
)
]
for
i
in
range
(
n
-
1
,
-
1
,
-
1
)
:
res
[
countArr
[
numList
[
i
]
]
-
1
]
=
numList
[
i
]
countArr
[
numList
[
i
]
]
-=
1
# 必须要减1，由于待排序元素在res中的位置是由计数数组的值来决定的。
# 当遍历了元素x之后，小于x的元素不会受影响，大于x的元素不会受影响，
# 只有等于x的元素会受影响，在往res中压的时候，要比x的位置往前移动一位，
# 因此需要将计数数组中的下标为x的值减1，使得下次在遍历到x的时候，
# 压入的位置在前一个x的位置之前
return
res
numlist
=
[
5
,
8
,
9
,
3
,
2
,
5
,
1
,
6
,
8
]
print
(
countingSort
(
numlist
)
)
# 输出结果为：[1, 2, 3, 5, 5, 6, 8, 8, 9]
