排序算法之计数排序

概述

简单来说, 计数排序就是申请一个相同数据范围的数组空间, 计算每个数字各有几个,如此即可.

如一个数组为: [5, 2, 3, 4, 6, 3, 1, 0]

申请一个长度为6的数组(因为数组范围为0-5), 其中的值为: [1, 1, 1, 2, 1, 1, 1]

其数组意思就是, 0有1个,1有1个, 类推

最后将其拼装为排序好的数组即可

通过描述可以看出, 这个排序不适合范围过大的数组, 如果有一个长度为2的数组: [1, 9999999999999], 虽然数组很短, 但是用计数排序的话, 计数数组也是十分大的. 而对于数字范围小, 且重复数字很多的情况, 那就很好了.

9e6effc964894eab9b91a50a99934a54 (1012×557)

其时间空间复杂度如下:

76bde39ff2354caa935ba0a2dff3eca9 (598×95)

Java代码实现

好吧, 计数排序很简单, 简单Java代码实现:

排序算法之计数排序

------------

原文地址 https://hujingnb.com/archives/176

转载请保留原文连接: 排序算法之计数排序 | 烟草的香味

guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x