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

admin2019-08-01 60

问题有一种简单的排序算法，叫做计数排序(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

学硕统考专业

明清时期继续采取“重农抑商”的政策，结果导致了()。

下列关于基督教的思想来源的叙述，不正确的是()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

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

()是清代管理边疆少数民族地区事务的机关，也掌管一部分外交事务。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

某计算机有五级中断L4～L0，中断屏蔽字为M4M3M2M1M0，Mi=1(0≤i≤4)表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3，则L1的中断处理程序中设置的中断屏蔽字是____。

假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度(电梯调度)算法得到的磁道访问序列是____。

解放生产力和发展生产力的关系是()

透明质酸酶不适合用于

下列凝血因子中，哪一个不是蛋白质

某哮喘患者，伴有严重房室传导阻滞和眼内压升高，应当选用

患者眩晕，精神萎靡，健忘多梦，腰膝酸软，四肢不温，形寒怯冷，舌质淡，脉沉细无力。治疗应首选()

在建筑物区分所有权的内容中，具有主导性的权利是()。

根据《中华人民共和国海关法》规定，在海关监管区和海关附近沿海沿边地区，海关有权检查、扣留有走私嫌疑的运输工具、货物、物品以及走私嫌疑人员。（）

下列关于诉讼时效中止的表述，正确的有()。

公共管理是以政府为核心的各类公共组织为保障和促进公共利益而提供公共产品和公共服务、管理公共事务的所有活动。公共管理的主体不仅包括国家行政机关，而且包括()。