有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表

admin2019-08-01 53

问题有一种简单的排序算法，叫做计数排序(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²次。简单选择排序算法比本算法好。简单选择排序的比较次数是n(n一1)／2，且只用一个交换记录的空间：而这种方法的比较次数是n²，且需要另一数组空间。

解析

转载请注明原文地址:https://kaotiyun.com/show/BjCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

关于亚历山大远征，下列说法中错误的是（）。

列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。

下列选项中，属于汉武帝时期削弱地方诸侯势力的措施是()。①推恩令②左官律③附益法④酎金夺爵

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

论述科举制度的演变及其历史作用。

赋税是我国古代国家宏观管理经济的重要手段。据此回答问题：西汉到北魏赋税制度的变化的基本趋势是()

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

下列软件中，属于应用软件的是

Isupposethatthemostbasicandpowerfulwaytoconnecttoanotherpersonistolisten.Justlisten.Perhapsthemostimportan

A．0～2岁B．2～3岁C．3～12岁D．12～13岁至成年E．成年后人类行为形成和发展的主动发展阶段一般在

学校制度是随便制定的，与国家和青少年的发展没多大的关系。

在教学方法改革过程中，布卢姆提出了()

设四维向量组α1=(1，1，4，2)T，α2=(1，－1，－2，b)T，α3(－3，－1，a，－a)T，β=(1，3，10，a+b)T问(1)当a，b取何值时，β不能由α1，α2，α3线性表出；(2)当a，b取何值时，β能由α1，α2，α3线性表出，

Olderpeoplemustbegivenmorechancestolearniftheyaretocontributetosocietyratherthanbeafinancialburden,accordi

有如下赋值语句：a=’’计算机’’，b=’’微型’’，结果为’’微型机’’的表达式是

TheoldladyletherflattoanEnglishcouple.