[每日一学] 计数排序——蓝桥杯培训
作者:CC下载站 日期:2020-04-29 00:00:00 浏览:59 分类:涨姿势
B站视频演示地址:https://www.bilibili.com/video/BV1GW411H7Cs/
概念:计数排序是一个非基于比较的排序算法,而是利用数组下标来确定元素的正确位置。用辅助数组对数组中出现的数字技术,元素转下标,下标转元素。
假设元素均大于等于0,一次扫描原数组,将元素值K记录在辅助数组的K位上。
1,基础版计数排序
假定20个随机整数的值如下:
9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9
创建一个辅助数组(长度为最大值+1)
先遍历这个无序的随机数列,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。
比如第一个整数是9,那么数组下标为9的元素加1:
第二个整数是3,那么数组下标为3的元素加1:
继续遍历数列并修改数组。。。。。。
最终,数列遍历完毕时,数组的状态如下:
遍历数组,输出数组元素的下标值,元素的值是几,就输出几次:
0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10
publicstaticvoidcountSort1(int[]arr){ intmax=arr[0]; for(inti:arr){ if(i>max){ max=i; } } int[]countarr=newint[max+1]; for(intj:countarr){ countarr[j]++; } intcurrent=0; for(inti=0;i<countarr.length;i++){ while(countarr[i]>0){ arr[current]=i; countarr[i]--; current++; } } }
2,改进版:
publicstaticvoidcountSort(int[]arr){ //找到arr的最大值和最小值 intmin=arr[0]; intmax=arr[0]; for(inti:arr){ if(i<min){ min=i; } if(i>max){ max=i; } } //创建计数数组 int[]countArr=newint[max-min+1]; for(intj:countArr){ countArr[j-min]++; } //定义指针 intcurrent=0; //回填 for(inti=0;i<countArr.length;i++){ while(countArr[i]>0){ arr[current]=i+min; current++; } } }
3,最终版
publicstaticint[]countArr3(int[]arr){ intmin=arr[0]; intmax=arr[0]; for(inti:arr){ if(i<min){ min=i; } if(i>max){ max=i; } } //创建计数数组 int[]countArr=newint[max-min+1]; for(intj:countArr){ countArr[j-min]++; } //对计数数组的元素进行累加,累加的规则将前一个元素的值+当前元素的值 for(inti=1;i<countArr.length;i++){ countArr[i]+=countArr[i-1]; } //创建一个数组,存储最终的有序数列 int[]sortedArr=newint[arr.length]; //回填 for(inti=arr.length-1;i>=0;i--){ sortedArr[countArr[arr[i]-min]-1]=arr[i]; countArr[arr[i]-min]--; } returnsortedArr; }
以上皆为笔记
猜你还喜欢
- 05-13 [摄影] 让手机秒变单反的手机拍摄好物
- 05-11 [摄影] 想挣钱的摄影师建议收藏!
- 05-11 [美食] 选址秘籍:从摆摊到开小店,大数据地图助你找到理想店铺位置
- 05-04 [知识分享] 「科普」不知道电影资源那么长一大串名字是什么意思?看完这个你就明白了!
- 04-30 [摄影] 玩转手机摄影 | 滤镜手机支架
- 04-30 [经验] 摆地摊的八大禁忌
- 04-27 [绘画] 油画棒原创作品【绽放】图文教程来咯~
- 04-17 [涨姿势] 餐饮管理故事:对不起,我订错了雅间,怎么办?(附解决方案)
- 03-29 [摄影课堂] 电光火石间的决定
- 03-29 [摄影相关] UV镜不要随便将就
- 03-29 [摄影技巧] 抗光害滤镜 | 还原城市最美夜景 城市夜空的色彩救星!
- 03-29 [设计] 无边泳池是怎么设计的?以及它的原理介绍
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[跨境电商] TikTok中视频课程30天线上陪跑
[电影] [摩登笑探 冇面俾].1995.HDTV1080i.国语中字
[电影] 非常偵探/The Private Eye Blues 1994
[摄影] 让手机秒变单反的手机拍摄好物
[电影](香港怀旧老电影)《情义我心知》1989.VCDRip.MKV[粤语双字]
[电影] [五个堕落的男女][HD-MKV/1.88G][国语中字][1080P]
[游戏娱乐] 《赤痕:夜之仪式》v1.50中文版
[游戏娱乐] 《极乐迪斯科》v20230509导演剪辑版
[电影] 2023年美国剧情片《包围》BD中英双字
[课程] 张景明教授《一病一讲·100集》
[资料] [大学期末救急课] 猴博士+高斯课堂+斐多课堂,全集视频合集
[云资源] 价值2万元的老男孩Python教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[云资源] 花了一千多元买的私人健身教程
[下载工具] Internet Download Manager 6.42.7 (IDM)
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[资料] 3000 套电影电视剧 LOGO 宣传片常用音效合集包
[安卓软件] 酷我音乐APP_v10.7.6.4 去广告破解豪华VIP版
[即时通讯] 微信PC版WeChat 3.9.9.43 多开防撤回绿色版
[安卓软件] Solid Explorer文件管理器APP 2.8.38 破解版
[云资源] 价值2万元的老男孩Python教程
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[云资源] 花了一千多元买的私人健身教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[动画] 北斗神拳(1984) [两季合集] [MKV]
[资料] 抗战阵亡将士资料+续编
[电视剧] 三体 (2024) 全8集 网飞版本 中文字幕 合集
[纪录片] 河西走廊【10集 国语 中文字幕 1080P 10.8G MP4】
[电影] 2024年喜剧片·热辣滚烫 [mp4]
[影视] 铁爪 WEB-DL版下载 2023 The Iron Claw 23.48G
- 最新评论
-
杂物房内的旧档资源不保证有效CC下载站 评论于:05-14 不能**123 评论于:05-14 我想看看mw2ddyy 评论于:04-26 好东西阿zfy123123 评论于:04-18 谢谢楼主xiaoqi 评论于:04-12 勿在线解压,勿手机解压,请在电脑上用最新款压缩软件解压!推荐360压缩或者好压CC下载站 评论于:04-10 无法解压啊,客服能不能给个解压教程ravengrey 评论于:04-10 谢谢支持!!CC下载站 评论于:03-26 很棒的资源,感谢分享云体风身 评论于:03-26 感谢分享,好东西云体风身 评论于:03-26
- 热门tag