52|计数排序:不通过比较也可以进行排序
王健伟
你好,我是王健伟。
前面我们学习了许多种类的排序,这次我带你学习一种不同思想的排序种类——桶思想排序。桶排序有什么不同吗?如果说前面的排序主要是通过关键字的比较和记录的移动,而桶思想的排序往往并不需要进行关键字的比较。
桶一般指生活里的一种容器,在这里其实是一个比较形象的说法,一般指排序过程中用到的诸如计数数组、辅助队列等用于临时容纳数据的地方。
这节课我将带你学习一下桶思想排序中的计数排序算法,计数排序算法有一定的编写技巧,我们将首先实现一个非稳定的计数排序算法,通过进一步改进代码来实现稳定的计数排序算法,让我们开始这次的学习旅程吧。
非稳定的计数排序算法的实现
计数排序是通过计数而不是比较来进行排序的。算法比较简单,适合于待排序记录数量多但排序关键字的范围比较小的整数数字排序情形。
比如某大型公司有 10 万名员工,按照员工年龄进行排序这种情形就非常适合计数排序。再比如有 1000 万人参加高考,满分 750 分,根据自己的分数来计算自己的名次,这也明显是一个排序问题,用计数排序也很合适。
计数排序的思想是创建一个新数组用于计数,数组的大小取决于要排序的关键字最大值是多少。比如大型公司的这个案例,排序关键字是年龄,而年龄一般不会超过 90 岁,所以这个新数组的大小为 90 即可。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
计数排序是一种高效的排序算法,它通过计数而不是比较来进行排序,适用于待排序记录数量多、排序关键字范围较小、整数数字排序的情况。该算法的时间复杂度为O(n+k),其中n为待排序元素数量,k为计数数组的大小。通过对代码进行改进,可以实现稳定的计数排序算法,但空间复杂度会由O(k)变为O(n+k)。文章详细介绍了计数排序的实现思路和稳定性问题,并给出了稳定计数排序的完整算法。此外,文章还提出了两个思考题,引导读者思考计数排序的适用场景和可能出现的性能问题。整体而言,该文章内容详实,适合读者快速了解计数排序算法的特点和实现方法。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(1)
- 最新
- 精选
- Bruder_Jin图2上面的那段话“代码中可以清晰地看到,后一个计数数组元素的值变成了当前值 + 前一个数组元素的值”,按照图2所示,应该是“当前值=当前值+前一位元素值”吧????2023-07-25归属地:广东
收起评论