首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
44
问题
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
设计实现计数排序的算法。对于有n个记录的表,关键字的比较次数是多少?与简单选择排序相比较,这种方法是否更好?为什么?
选项
答案
typedef struct{ int key; datatype info }RecType: void CountSort(RecType a[],b[],int n){ //计数排序算法,将a中记录排序放入b中 int i,j,cnt: for(i=0;i<n;i++){ //对每一个元素 for(j=0,cnt=0;j<n;j++) if(a[j].key<a [i].key)cnt++; //统计关键字比它小的元素个数 B[cnt]=a[i]; } } 对于有n个记录的表,关键字比较n
2
次。 简单选择排序算法比本算法好。简单选择排序的比较次数是n(n一1)/2,且只用一个交换记录的空间:而这种方法的比较次数是n
2
,且需要另一数组空间。
解析
转载请注明原文地址:https://kaotiyun.com/show/BjCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
下列各组古代民族,其语言都属于印欧语系的是()
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
重庆谈判中蒋介石始终不承认人民军队和解放区的合法地位,其根本目的是()。
日本法西斯与德国法西斯相比,突出的特点是()
红山文化的代表性墓葬形式为()。
1946年3月5日,英国前首相丘吉尔在富尔敦发表了(),发出第一个明白无误的“冷战”信号。
系统阐明社会主义初级阶段理论是在()。
某计算机系统的内存储器由Cache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:(1)Cache的命中率是多少?(2)CPU访问内存的平均
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
随机试题
OIML国际建议属于___________。
关于清热药,指出下列错误的是
下列哪一项不属于胃切除术后近期并发症?()
单层厂房结构,柱间支撑的主要作用是()。
______ananswer,theydecidedtosendanexpresstelegramtothem.
Generallyspeaking,aBritishiswidelyregardedasaquiet,shyandconservativepersonwhois【B1】______onlyamongthosewith
窗体“滚动条”属性值有【】个选项。
A、0.15%B、1.5%C、15%D、150%B第二段中提到“113个环保重点城市空气优良天数增加了1.5个百分点”,所以选B。
A、Tothemovie.B、Tohersister’shome.C、Totherailwaystation.D、Totheticketoffice.C本题问的是“这位女士要去哪”,对话中提到Ihavetogoto
A、Tohaveherteethfilled.B、Tohaveherteethpulled.C、Tohaveherteethcleaned.D、Tohaveherteethexamined.A选项均以不定式开头以及选
最新回复
(
0
)