首页
下载应用
提交文章
关于我们
问卷:你怎么看自由微信?
🔥 热搜 🔥
1
上海
2
习近平
3
新疆
4
鄂州父女瓜
5
乌鲁木齐
6
疫情
7
H工口小学生赛高
8
习明泽
9
芊川一笑图包
10
印尼排华
分类
社会
娱乐
国际
人权
科技
经济
其它
首页
下载应用
提交文章
关于我们
问卷:你怎么看自由微信?
🔥
热搜
🔥
1
上海
2
习近平
3
新疆
4
鄂州父女瓜
5
乌鲁木齐
6
疫情
7
H工口小学生赛高
8
习明泽
9
芊川一笑图包
10
印尼排华
分类
社会
娱乐
国际
人权
科技
经济
其它
白石洲拆迁后,那些上学奔波的孩子都去哪儿了?
一个医保局长之死
给宠物做保姆的中国留学生
本以为吴京大儿子叫“吴所谓”够随意了,听到二儿子名字,真服了
法院4.2元拍卖一瓶雪碧,限自提!被执行人回应:没有更多可供执行财产
生成图片,分享到微信朋友圈
查看原文
其他
虽然小象被淘汰了,但我学会了这种O(n)的排序算法
Original
KG沈剑
架构师之路
2022-07-22
收录于合集
#算法
17 个
#面试
13 个
#互联网
48 个
#架构
78 个
时间复杂度为O(n)的排序,除了昨天介绍的
基数排序
(Radix Sort)
,还有
计数排序
(Counting Sort)
。
计数排序的适用范围?
待排序的元素在某一个范围
[MIN, MAX]
之间。
画外音:很多业务场景是符合这一场景,例如uint32的数字排序位于[0, 2^32]之间。
计数排序的空间复杂度?
计数排序需要一个辅助空间,空间大小为
O(MAX-MIN)
,用来存储所有元素出现次数(“计数”)。
画外音:计数排序的核心是,空间换时间。
计数排序的关键步骤?
步骤一
:扫描待排序数据
arr[N]
,使用计数数组
counting[MAX-MIN]
,对每一个
arr[N]
中出现的元素进行计数;
步骤二
:扫描计数数组
counting[]
,还原
arr[N]
,排序结束;
举个
栗子
:
假设待排序的数组,
arr={5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6}
很容易发现,待排序的元素在
[0, 10]
之间,可以用
counting[0,10]
来存储计数。
第一步:统计计数
扫描未排序的数组
arr[N]
,对每一个出现的元素进行计数。
扫描完毕后,计数数组
counting[0, 10]
会变成上图中的样子,如粉色示意,
6
这个元素在
arr[N]
中出现了
4
次,在
counting[0, 10]
中,
下标为6
的位置
计数是4
。
第二步:还原数组
扫描计数数组
counting[0, 10]
,通过每个元素的计数,还原
arr[N]
。
如上图粉色示意,
count[0, 10]
下标为6
的位置
计数是4
,排完序是
4个连续的6
。
从counting下标MIN到MAX,逐个还原,填满
arr[N]
时,排序结束。
神奇不神奇!!!
计数排序
(Counting Sort)
,总结:
(1)计数排序,时间复杂度为O(n);
(2)当待排序元素个数很多,但值域范围很窄时,计数排序是很节省空间的;
希望这一分钟,大家有收获。
架构师之路
-分享可落地的技术文章
相关文章
:
《
基数排序,一个O(n)的排序算法
》
作业题
:
还有哪些时间复杂度为O(n)的排序算法呢?
您可能也对以下帖子感兴趣
{{{title}}}
文章有问题?点此查看未经处理的缓存