第 28 题:如何理解计数排序?
2021/8/21 13:06:03
本文主要是介绍第 28 题:如何理解计数排序?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
什么是计数排序?
计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数
计数排序最重要的一点,确定范围的整数,比如说范围 0-10,那么数组里面的值就要在 0-10 之间
栗子
序列:9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9 ,7,9
首先确定序列的范围是 0-10,并且列出范围的序列,如图 1
比如第一个整数是 9,那么数组下标为 9 的元素加 1
#图 1
第二个整数是 3,那么数组下标为 3 的元素加 1,如图 2
#图 2
以此类推重复遍历…
最终遍历完成后状态如下,如图 3
#图 3
数组每一个下标位置的值,代表了在序列中对应整数出现的次数
有了这个“统计结果”,排序就很简单了。直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次
0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10
最后输出的序列已经是排好序的
这个时候可能会有人问,如果序列的最小值不是从 0 开始呢?
这个时候就要计算偏移量
如何计算偏移量?
以序列的最小值作为偏移量。比如最小值是 90, 那么整数 95 对应的统计数组下标就是 95-90 = 5
这篇关于第 28 题:如何理解计数排序?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南