counting sort 的管窥

摘自wikipedia:
count sort 计数排序 稳定的线性时间排序法
计数排序不是比较排序，排序的速度快于任何比较排序算法。
统计出有多少元素小于或等于某一个元素，也就知道该元素的正确得位置。
1.定新数组大小——找出待排序的数组中最大和最小的元素
2.统计次数——统计数组中每个值为i的元素出现的次数，存入新数组C的第i项
3.对统计次数逐个累加——对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4.反向填充目标数组——将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

分类 排序算法
数据结构 数组
最坏时间复杂度 O(n+k)
最优时间复杂度 O(n+k)
平均时间复杂度 O(n+k)

计数排序是不存在比较和交换等一般排序的思想，而是如同”萝卜占坑“的样子。

将数列中最大数和最小数差值构建从最达到最小的长度序列，然后统计各个数字的个数，并根据下标和数字的个数进行从小到大进行扩充。
分析：这种排序不存在比较和交换，只需要根据统计的数字个数进行从低到高的排序就行了。所以，时间复杂度是线性的递增，但是空渐渐复杂度趋势较高，但是排序算法是稳定的。
下面是python3的计数排序算法代码：`

def counting_sort(collection):# 待排序数列的长度length = len(collection)# 获得待排序数列的最大值和最小值，并构建相应的计数数列coll_max = max(collection)coll_min = min(collection)calc_list = [0]*(coll_max+1-coll_min)# 将相应的数字的个数统计记录在统计数字个数列表中for num in collection:calc_list[num] += 1output_list = []# 将数字的个数和其表示数字的下标进行扩充有序的数列for i in range(len(calc_list)):while calc_list[i]:output_list.append(i)calc_list[i] -= 1return output_listif __name__ == "__main__":user_input = input('Enter numbers separated by a comma:\n').strip()unsorted = [int(item) for item in user_input.split(',')]print(counting_sort(unsorted))

同时关于计数排序方法还有其他的方式解决，但是主要思想都是基于这样的思想。