[每日一学] 计数排序——蓝桥杯培训
作者:CC下载站 日期:2020-04-29 00:00:00 浏览:75 分类:涨姿势
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; }
以上皆为笔记
猜你还喜欢
- 06-29 [涨姿势] 鱼丸批量化生产流程,什么是鱼丸加工流水线?都有哪些设备组成?
- 06-29 [涨姿势] 食为先培训的陷阱和套路?凉菜不是你想卖就能卖?
- 06-29 [涨姿势] 开面馆不是梦,但也不是人人都能驾驭
- 05-13 [摄影] 让手机秒变单反的手机拍摄好物
- 05-11 [摄影] 想挣钱的摄影师建议收藏!
- 05-11 [美食] 选址秘籍:从摆摊到开小店,大数据地图助你找到理想店铺位置
- 05-04 [知识分享] 「科普」不知道电影资源那么长一大串名字是什么意思?看完这个你就明白了!
- 04-30 [摄影] 玩转手机摄影 | 滤镜手机支架
- 04-30 [经验] 摆地摊的八大禁忌
- 04-27 [绘画] 油画棒原创作品【绽放】图文教程来咯~
- 04-17 [涨姿势] 餐饮管理故事:对不起,我订错了雅间,怎么办?(附解决方案)
- 03-29 [摄影课堂] 电光火石间的决定
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[电影] 《环太平洋两部合集》 4K REMUX原盘 [杜比视界] 国英双语音轨 [内封特效字幕] [133.8G]
[电影] 异人之下 The Traveller 2024✨【影版】【4K正式版/HQ超高码/DDP5.1】✚【1080高码】无水印/无压缩
[动漫] 头文字D 动漫 (1998) S01-S06季 1080P 国粤日音轨 续作 剧场版 电影
[小说] 知轩藏书全站7667册txt小说合集精心校对版
[杂志] 电脑爱好者杂志14年 超全 [PDF]
[电影] 西游记全部版本-4K高清修复-总计384G-1986+1996+1998+2002+2010浙版+西游记后传
[纪录片] 【国家地理百年纪念典藏】超经典100集全 MP4格式 (绝佳学习资料)27GB
[纪录片] B站食贫道收费纪录片 *迷失东京* [1080P] 揭露日本大家感兴趣却不为人知的秘密
[网络线报] 城通网盘福利线报解析器 - 获取直连下载地址
[福利线报] 一个「脚本」搞定六大网盘(百度/阿里/天翼/迅雷/夸克/移动)
[游戏] 《黑神话悟空》免安装学习版【全dlc整合完整版】+Steam游戏解锁+游戏修改工具!
[动画] 《名侦探柯南》名侦探柯南百万美元的五菱星 [TC] [MP4]
[电视剧集] [BT下载][黑暗城市- 清扫魔 Dark City: The Cleaner 第一季][全06集][英语无字][MKV][720P/1080P][WEB-RAW]
[涨点姿势] 男性性技宝典:14招实战驭女术——爱抚、按摩、催情、姿势、高潮全攻略
[动画] 2002《火影忍者》720集全【4K典藏版】+11部剧场版+OVA+漫画 内嵌简日字幕
[剧集] 《斯巴达克斯》1-4季合集 无删减版 1080P 内嵌简英特效字幕
[CG剧情] 《黑神话:悟空》158分钟CG完整剧情合集 4K120帧最高画质
[短剧] 被下架·禁播的羞羞短剧·午夜短剧合集
[游戏] 黑神话悟空离线完整版+修改器
[图像处理] 光影魔术手v4.6.0.578绿色版
[影视] 美国内战 4K蓝光原盘下载+高清MKV版/内战/帝国浩劫:美国内战(台)/美帝崩裂(港) 2024 Civil War 63.86G
[影视] 一命 3D 蓝光高清MKV版/切腹 / 切腹:武士之死 / Hara-Kiri: Death of a Samurai / Ichimei 2011 一命 13.6G
[影视] 爱情我你他 蓝光原盘下载+高清MKV版/你、我、他她他 2005 Me and You and Everyone We Know 23.2G
[影视] 穿越美国 蓝光原盘下载+高清MKV版/窈窕老爸 / 寻找他妈…的故事 2005 Transamerica 20.8G
[电影] 《黄飞鸿》全系列合集
[Android] 开罗游戏 ▎像素风格的模拟经营的游戏厂商安卓游戏大合集
[游戏合集] 要战便战 v0.9.107 免安装绿色中文版
[资源] 精整2023年知识星球付费文合集136篇【PDF格式】
[系统]【黑果小兵】macOS Big Sur 11.0.1 20B50 正式版 with Clover 5126 黑苹果系统镜像下载
[美图] 【经典收藏美图集合】1500多张韩国美女高清图片让你的收藏夹更加丰富多彩
- 最新评论
-
有靳东!嘻嘻奥古斯都.凯撒 评论于:10-28 流星花园是F4处女作也是4人集体搭配的唯一一部!奥古斯都.凯撒 评论于:10-28 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢AAAAA 评论于:10-26 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢password63 评论于:10-26 找了好久的资源,终于在这里找齐了!!!!blog001 评论于:10-21 找了好久的资源,终于在这里找齐了!!!!blog001 评论于:10-21 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢WillKwok 评论于:10-09 感谢分享1234123 评论于:10-07 太好了终于找到了谢谢Tom 评论于:10-07 谢谢分享loonghd 评论于:09-30
- 热门tag