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

admin2019-08-01 69

问题有一种简单的排序算法，叫做计数排序(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://www.kaotiyun.com/show/BjCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列明末清初来华传教士，按时间顺序排列，正确的是（）。

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

曾在1978年5月10日《理论动态》上发表的《实践是检验真理的唯一标准》一文，以后又在《光明日报》、《人民日报》、《解放军报》转载，这篇文章的初稿作者是()。

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

影片《大独裁者》、《摩登年代》的作者是（）

下列关于类风湿关节炎关节表现的叙述，错误的是

A、苍术、陈皮、厚朴、甘草B、茵陈、栀子、大黄C、猪苓、茯苓、泽泻、阿胶、滑石D、猪苓、茯苓、泽泻、桂枝、白术E、附子、生姜、白术、茯苓、白芍猪苓汤的组成是

某县在2003年春的义务献血活动中，除了公民个人献血外，党政机关、驻军官兵、中小学教师及部分学生也以单位组织献血，其中不属于国家提倡的献血年龄是

等电位联结带之间和等电位联结带与接地装置之间的连接导体，流过大于或等于25％，总雷电流的等电位联结导体铁的最小截面为()。

成本计算账户是专门用来核算一定时期内所发生的应计入当期损益的各项费用损失和支出的账户。()

甲乙签订一份买卖合同，约定违约方应向对方支付18万元违约金。后甲违约，给乙造成损失15万元。根据合同法律制度的规定，下列说法正确的是()。

依照我国公司法的规定，股份有限公司董事会的组成人数是()人。

一般而言，股份制金融机构资金成本最高的筹资方式是()。