一、计数排序
这种排序算法 是利用数组下标来确定元素的正确位置的。
如果数组中有20个随机整数，取值范围为0~10，要求用最快的速度把这20个整数从小到大进行排序。 很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn）的排序。
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9，7，9
考虑到这些整数只能够在0、1、2、3、4、5、6、7、8、9、10这11个数中取值，取值范围有限。可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0
下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时对应数组下标的元素进行加1操作。
根据这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标 值，元素的值是几，就输出几次: 0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
计数排序的基本过程，它适用于一定范围内的整数排序。在取值范围不是 很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn）的排序。
def countSort(ll):
# 1.得到数列的最大值
max=ll[0]
for i in range(1,len(ll)):
if ll[i]>max:
max=ll[i]
# print(max)
# 2.根据数列最大值确定统计数组大小,并赋值0；
arrs=[0]*(max+1)
print(arrs)
# 3.遍历数列,填充统计数组
for i in range(len(arrs)):
arrs[ll[i]]+=1
print(arrs)
# 4.遍历数列
sorted_arrs=[]
for i in range(len(arrs)):
for j in range(0,arrs[i]):
# print(i)
sorted_arrs.append(i)
#返回排序数组
return sorted_arrs
if __name__ == '__main__':
ll=[9,3,5,4,9,1,2,7,8,1,10]
print(ll)
print(countSort(ll)) 
以上是找数列的最大值来决定统计数组的长度，其实并不严谨 。
如： 96，93，91，94，95，90，99, 93，91，90
这个数列的最大值是99，但最小的整数是90。如果创建长度为100的数组，那么前面从0到89的空间位置就都浪费了!
很简单，只要不再以输入数列的最大值+1作为统计数组的长度，而是以数列最大值-最小值+1作为统计数组的长度即可。 同时数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。
统计出数组的长度：99-90+1=10，偏移量等于数列的最小值90对于第1个整数96，对应的统计数组下标是96-90=6
如下图所示: 同时数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。
如果学生成绩表，要求按成绩从低到高进行排序，如果成绩相同，则遵循原表固有顺序。
如图所示：
这是变形，其实就是从统计数组的第2个元素开始，每一个元素都加上前面所有元素之和。
步骤1：遍历成绩表最后一行的小绿同学的成绩。
小绿的成绩是95分，找到count_array下标是5的元素，值是4，代表小绿的成绩排名位置在第4位。 同时，给count_array下标是5的元素值减1，从4变成3，代表下次再遇到95分的成绩时，最终排名是第3。
步骤2：遍历成绩表倒数第二行的小白同学的成绩。
步骤3：遍历成绩表倒数第三行的小红同学的成绩。
重复上面的步骤继续完成！
'''优化'''
def countSort2(ll):
# 1.得到数列的最大值,最小值
max=ll[0]
min=ll[0]
for i in range(1,len(ll)):
if ll[i]>max:
max=ll[i]
if ll[i]<min:
min=ll[i]
#差值
diff=max-min
# print(diff)
# 2.确定统计数组大小,并赋值0；
arrs=[0]*(diff+1)
# print(arrs)
# 3.遍历数列,填充统计数组
for i in range(len(ll)):
arrs[ll[i]-min]+=1 #如：95-90=5,94-90=4
print(arrs)
# 4.统计数组变形，从第二个元素开始，后面的元素等于前面的元素之和
for i in range(1,len(ll)):
arrs[i]+=arrs[i-1] #1+2,3+1,4+1...
print(arrs)
# 5.排序数列
sorted_arrs=[0]*len(ll)
# 倒序遍历原始数列，从统计数组找到正确位置
for i in range(len(ll)-1,-1,-1):
sorted_arrs[arrs[ll[i]-min]-1]=ll[i] #92-90-1=1；1是排序数列下标，再将对应原始数据最后一个赋值到这个下标。
arrs[ll[i] - min] -= 1 #arrs[92-90]-1=arrs[2]-1=1
# #返回排序数组
return sorted_arrs
if __name__ == '__main__':
ll = [95,94,91,98,99,90,99,93,91,92]
print(ll)
print(countSort2(ll))
计数排序有它的局限性，主要表现两点：
1、当数列最大和最小值差距过大时，并不适合用计数排序。
如：给出20个随机整数，范围在0到1亿之间，这时如果使用计数排序，需要创建长度为1亿的数组。不但严重浪费空间，而且时间复杂度也会随之升高。
2、当数列元素不是整数时，也不适合用计数排序。
如果数列中的元素都是小数，如25.213或0.000001这样的数字，则无法创建对应的统计数组。