排序算法（5）——计数排序
计数排序
概念：
计数排序是一种非比较性的排序算法，元素排序的过程，由额外内存空间的调用和元素本身值的范围大小决定。计数排序过程中没有元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到额外空间后，通过对额外空间内数据的计算来移动元素，就可以将数组排序完毕。
局限性：
（1）作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
（2）当数组的最大和最小值差距过大时，会造成过多额外浪费空间，并不适用计数排序。
算法步骤：
（1）计算待排序集合中最大元素和最小元素的差值加1，以此大小申请额外空间；
（2）遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间C内（也就是额外空间内次数记录的索引就是这元素值）；比如：（1,2，4,2，5）
| 次数 |
1 |
2 |
0 |
1 |
1 |
| 元素（索引） |
1 |
2 |
none |
4 |
5 |
（3）对额外空间内数据进行累加计算（当前位置=当前次数+前一个次数）得到更新的列表C；
| 元素位置 |
1 |
3 |
3 |
4 |
5 |
| 元素（索引） |
1 |
2 |
none |
4 |
5 |
（4）反向填充目标列表：将每个元素i放在新列表的第C(i)项，每放一个元素就将C(i)减去1
算法复杂度：
时间复杂度----平均： O(n + k) | 最坏：O(n + k) | 最好：O(n + k)
(n为元素数量，k为元素最大值与最小值之差加1)
空间复杂度----O(n + k)
稳定性----稳定
实例：
（1）此种写法，当数据不多却离0值太远时会造成极大空间浪费。
def count_sort(list):length = len(list)if length < 2:return listmax_num = max(list)count = [0] * (max_num + 1) # 创建额外空间来计数for element in list:count[element] += 1out_list = [] # 根据计数结果来把元素放置到对应位置for i in range(max_num + 1):for j in range(count[i]): # count[i]表示元素i出现的次数，如果有多次，通过循环重复追加out_list.append(i)return out_list
（2）优化空间写法，当数据不从比较接近0开始时，可以节省一部分空间。
def count_sort(ls):max_value, min_value = max(ls), min(ls)# 申请额外空间用来记录元素出现的次数count_ls = [0] * (max_value - min_value + 1)for i in ls:# 最小值即为索引0，这样计数就比直接按每个元素为索引节省部分空间count_ls[i - min_value] += 1# 计算每个元素的位置for i in range(1, len(count_ls)):count_ls[i] += count_ls[i-1]target_ls = [None] * len(ls)# 反向遍历索引是为了保持算法的稳定性for i in range(len(ls) - 1, -1, -1):# 因为之前设定了最小值的索引为0count_index = ls[i] - min_value# 以下相当于根据索引记录把元素按顺序放入目标列表target_ls[count_ls[count_index] - 1] = ls[i]# 每放了一个元素计数就减一，主要是用来避免出现空元素位置（应该在空元素索引的位置放入出现多次的元素）。count_ls[count_index] -= 1return target_lsif __name__ == '__main__':ls = [1, 2, 4, 2, 5]print(ls)sort_ls = count_sort(ls)print(sort_ls)
以上若描述有误，还请留言指出，谢谢！