计数排序算法
原创
计数排序算法是一种典型的以空间换时间的一种算法。 这种算法主要是适合于正整数进行 排序。还是比较好理解的，而且在很多场合确实能提高效率。
计数的关键点:
- 数组中的数据是正整数
- 找出数组中的最大值,建立一个下标辅助数组
- 统计待排序数组在下标辅助数组中出现的次数
- 遍历下标辅助数组
举例说明一下计数排序的过程, 以数组: 6, 7, 4, 3, 8为例
- 找出数组最大值为8。
- 建立一个长度为9（最大值+1）b的辅助数组。
- 统计3, 4, 6, 7, 8 数组值为下标的index的值的个数， b[3]= 1, b[4]=1,b[6]=1,b[7]=1,b[8]=1
- 遍历数组b把不为0的数赋值给原数据，可以得到排序结果 3,4,6,7,8
以下是python代码实现的计数排序
def count_sort(elements):
ma = -1
for e in elements:
if ma < e:
ma = e
index = [0]*(ma + 1)
for e in elements:
index[e] = index[e] + 1
j = 0
for i in range(len(index)):
while index[i] > 0:
elements[j] = i
index[i] = index[i] - 1
j = j + 1
if __name__ == '__main__':
arr = [6, 7, 4, 3, 8]
count_sort(arr)
print(arr)运行结果如下：
[3, 4, 6, 7, 8]
更多内容请关注公众号：IT技术漫漫谈
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
腾讯云开发者
