算法----计数排序(最容易理解和实现的排序之一)

原创 lronelove 随笔 算法笔记 121阅读 2019-02-01 16:51:50 举报

1. 什么是计数排序

假设我们现在有一个数组:

我们分别统计一下不大于每个元素的个数,例如:
小于等于1的个数:1
小于等于2的个数:2
小于等于3的个数:3

那么我们就可以根据这个统计的个数,来依次插入到另一个新数组里面
比如,这里有一个空的数组

那么,根据统计,小于等于2的个数有2个,所以

依次,根据统计,小于等于1的个数只有1个,所以

最后,根据统计,小于等于3的个数有3个,所以,

最终得到:

像这样的,统计每个数出现的次数,依此来进行排序的就是计数排序。

2. 实现的细节

我们大概清楚计数排序的原理之后,我们来看下代码里面具体如何去实现它,以及对应的细节。

  • 存放统计的数组:
    首先,我们需要统计,那么必须有一个数组countArray来存放统计的数据,数组的长度一定要大于,需要排序的数组array的最大值,因为后面array里面的每一个元素,都会对应于countArray里面的一个下标。
    初始值,为0
  • 存放排序完成的数组:当统计完毕之后,需要一个数组来根据统计的结果来插入元素。
    好,现在基本细节大概介绍了下,可以介绍下代码了。

3.具体实现代码

大概分为四个部分:

  • 根据array的最大值来创建,countArray,长度为max+1(数组下标以0开始),默认值为0。
  • 统计每个数出现的个数。
  • 统计小于等于某个数的个数,依次累加
  • 根据统计,依次把array[i]放在对应的位置里面。每次加完之后,记得进行减1操作

4. 杂记

计数排序的总的时间代价是O(n + max),大家有兴趣也可以了解下。
谢谢,各位新年快乐~

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复