1、计算机专业基础综合（排序）-试卷 2及答案解析(总分：68.00，做题时间：90 分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.采用简单选择排序，比较次数与移动次数分别为( )。（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n)D.O(nlog 2 n，)，O(n)3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（分数：2.00）A.堆排序归并排序快速排序D.堆排序快速排序归并排
2、序4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5个长度为 2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（分数：2.00）A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，825.已知 10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（分数：
3、2.00）A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，956.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，2l，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，
4、47，68，84 其所采用的排序方法是( )。（分数：2.00）A.直接选择排序B.希尔排序C.归并排序D.快速排序7.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第 7个记录 60插入到有序表时，为寻找插入位置需比较( )次。（分数：2.00）A.1B.2C.3D.48.将两个各有 N个元素的有序表归并成一个有序表，其最少的比较次数是( )。（分数：2.00）A.NB.2N-1C.2ND.N-19.已知待排序的 n个元素可分为 nk 个组，每个组包含 k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比
5、较的排序，其时间下界应为( )。（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 n)C.O(klog 2 n)D.O(klog 2 k)10.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1911.归并排序中，归并的趟数是( )。（分数：2.00）A.O(n)B.O(log 2 n)C.O(
6、nlog 2 n)D.O(n 2 )12.有一组数据(15，9，7，8，20，-1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（分数：2.00）A.-1，4，8，9，20，7，15，7B.-1，7，15，7，4，8，20，9C.-1，4，7，8，20，15，7，9D.A、B、C 均不对13.基于比较方法的 n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。（分数：2.00）A.O(nlog 2 n)B.O(log 2 n)C.O(n)D.O(n 2 )14.以下排序方法中，稳定的排序方法是( )。（分数：2.00）A.直接插入排序B.直接选择排序C.堆排序D.基数排序
7、15.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定 d 0 =9，d 1 =4，d 2 =2，d 3 =1，则第二趟排序结束后前 4条记录为( )。（分数：2.00）A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40)D.(15，20，80，70)16.在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（分数：2.00）A.5，4，8B.6，3，9C.7，4，3D.3，8，2二、综合应用题(总题数：11，分数：36.00)17.
8、综合应用题 41-47小题。_18.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?（分数：2.00）_19.设有 5个互不相同的元素 a，b，c，d，e，能否通过 7次比较就将其排好序?如果能，请列出其比较过程：如果不能，则说明原因。（分数：2.00）_20.对一个由 n个关键字不同的记录构成的序列，能否用比 2n一 3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?（分数：2.00）_21.利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么
9、?请给出详细证明。（分数：2.00）_已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?（分数：8.00）(1).关键字自小到大有序(key 1 kye 2 key n )；（分数：2.00）_(2).关键字自大到小逆序(key 1 key 2 key n )；（分数：2.00）_(3).奇数关键字顺序有序，偶数关键字顺序有序(key 1 key 3 ，key 2 key 4 )；（分数：2.00）_(4).前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1 key 2 key m ，
10、key m+1 key m+2 key n ，m 为中间位置)。（分数：2.00）_对于 n个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n个元素的初始排序有关。问：（分数：8.00）(1).当 n=7时，在最好情况下需进行多少次比较?请说明理由。（分数：2.00）_(2).当 n=7时，给出一个最好情况的初始排序的实例。（分数：2.00）_(3).当 n=7时，在最坏情况下需进行多少次比较?请说明理由。（分数：2.00）_(4).当 n=7时，给出一个最坏情况的初始排序的实例。（分数：2.00）_关于堆的一些问题：（分数：6.00）(1).堆的存储表示是顺序的，还是链接的?（分数
11、：2.00）_(2).设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?（分数：2.00）_(3).对 n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 O表示法)?（分数：2.00）_22.若有 N个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 ，请用文字简要说明如何在 log 2 n的时间内将其重新调整为一个堆。（分数：2.00）_23.冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。（分数：2.00）_24.有一种简单的排序算法，叫做计
12、数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。 设计实现计数排序的算法。对于有 n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?（分数：2.00）_计算机专业基础综合（排序）-试卷 2答案解析(总分：68.00，做题时间：90 分钟)一、单项
13、选择题(总题数：16，分数：32.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.采用简单选择排序，比较次数与移动次数分别为( )。（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n) D.O(nlog 2 n，)，O(n)解析：解析：简单选择排序的关键字比较次数 KCN与对象的初始排列无关。第 i趟选择具有最小关键字对象所需的比较次数总是 ni1次(此处假定整个待排序对象序列有 n个对象)。因此，总的关键字比较次数为：3.就排序算法所用的辅助空间而言
14、，堆排序、快速排序、归并排序的关系是( )。（分数：2.00）A.堆排序归并排序快速排序D.堆排序快速排序归并排序解析：解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为 O(1)，快速排序为 O(log 2 n)，归并排序为 O(n)。应选 A。4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5个长度为 2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（分数：2.00）A.16，25，35，48，23，40，79，82，36，72 B.16，25，35，48，79，82，23，36，40，72C.16，25，48，3
15、5，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为 A。5.已知 10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（分数
16、：2.00）A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95 C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，95解析：解析：冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选 B。6.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，2l，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20
17、，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00）A.直接选择排序 B.希尔排序C.归并排序D.快速排序解析：解析：可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为 A。7.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第 7个记录 60插入到有序表时，为寻找插入位置需比较( )次。（分数：2.00）A.1B.2C.3 D.4解析：解析：第 6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入 60，要与 95、7
18、0 和 50进行比较，共比较 3次，本题答案为 C。8.将两个各有 N个元素的有序表归并成一个有序表，其最少的比较次数是( )。（分数：2.00）A.N B.2N-1C.2ND.N-1解析：解析：此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为。9.已知待排序的 n个元素可分为 nk 个组，每个组包含 k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 n) C.O(klog 2 n
19、)D.O(klog 2 k)解析：解析：此题考查的知识点是分块排序的思想。因组与组之间已有序，故将 n/k个组分别排序即可，基于比较的排序方法每组的时间下界为 O(klog 2 k)。可以用二叉树分治形式描述，最好的情况是树的高度为 log 2 k。全部时间下界为 O(nlog 2 k)。应选 B。10.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D
20、.3，12，5，8，28，20，15，22，19解析：解析：根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：11.归并排序中，归并的趟数是( )。（分数：2.00）A.O(n)B.O(log 2 n) C.O(nlog 2 n)D.O(n 2 )解析：解析：此题考查的知识点是归并排序。第 1遍归并的子序列长度为 2 0 ，第 2遍为 2 1 ，第i遍为 2 i-1 ，所以由 2 i-1 n 知，对 n个记录的数据集合，总共需要归并 log 2 n次。应选 B。12.有一组数据(15，9，7，8，20，-1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（分数：2.00）A.
21、-1，4，8，9，20，7，15，7B.-1，7，15，7，4，8，20，9C.-1，4，7，8，20，15，7，9 D.A、B、C 均不对解析：解析：此题考查的知识点是堆排序。应选 C。13.基于比较方法的 n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。（分数：2.00）A.O(nlog 2 n) B.O(log 2 n)C.O(n)D.O(n 2 )解析：解析：此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行 log 2 (n!)次比较。 由 Stirling公式可知，log 2 (n!)nlog 2 n一1
22、44n+O(log 2 n)。所以基于关键字比较的分类时间的下界是 O(nlog 2 n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选 A。14.以下排序方法中，稳定的排序方法是( )。（分数：2.00）A.直接插入排序 B.直接选择排序C.堆排序D.基数排序解析：解析：下表为各种排序方法的性能比较。由表可知，本题答案为 A。15.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定 d 0 =9，d 1 =4，d 2 =2，d 3 =1，则第二趟排序结束后前 4条记录为( )。（分数：2.00）A.(50，20，15，70)B.(60，45
23、，80，50)C.(15，20，50，40) D.(15，20，80，70)解析：解析：t=3，d 0 =9，d 1 =4，d 2 =2，d 3 =1，第 1趟(d 1 =4)后的结果为(15，40，60，20，50，70，95，45，80)，第 2趟(d 2 =2)后的结果为(15，20，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。16.在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（分数：2.00）A.5，4，8 B.6，3，9C.7，4，3D.3，8，2解析：解
24、析：n=20，共需进行log 2 n=5趟归并，第 1趟归并后成为 10个有序表，第 2趟归并后成为 5个有序表(每个长度为 4)，第 3趟归并将长度为 4个的有序表归并为长度为 8的有序表，本题答案为：5，4，80二、综合应用题(总题数：11，分数：36.00)17.综合应用题 41-47小题。_解析：18.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?（分数：2.00）_正确答案：(正确答案：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化，而题中叙述和排序中稳定性的定义无关
25、，所以此说法不对。)解析：19.设有 5个互不相同的元素 a，b，c，d，e，能否通过 7次比较就将其排好序?如果能，请列出其比较过程：如果不能，则说明原因。（分数：2.00）_正确答案：(正确答案：可以做到。取 a与 b进行比较，c 与 d进行比较。设 ab，cd(abd；若 bdb，此时已进行了 3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 4次比较，从而共需 7次比较。)解析：20.对一个由 n个关键字不同的记录构成的序列，能否用比 2n一 3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?（分数：2
26、.00）_正确答案：(正确答案：将 n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较比较中的小者放前半部，大者放后半部，用了 n2 次比较。再在前后两部分中分别简单选择最小和最大元素，备用(n2)一 1次比较。总共用了(3n/2)一 2次比较。显然，当 n3 时，(2n一 3)(3n2)一 20 用分治法求解再给出另一参考答案。 对于两个数 x和 y，经一次比较可得到最大值和最小值；对于三个数 x，y，z，最多经 3次比较可得最大值和最小值；对于 n个数(n3)，将分成长为n一 2和 2的前后两部分 A和 B，分别找出最大者和最小者：Max A，Min 4，Ma
27、x B，MinB，最后Max=Max A，Max B和 Min=Min A，Min B。对 A使用同样的方法求出最大值和最小值，直到元素个数不超过 3。 设 C(n)是所需的最多比较次数，根据上述原则，当孔3 时有如下关系式： )解析：21.利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。（分数：2.00）_正确答案：(正确答案：假定待排序的记录有 n个。由于含 n个记录的序列可能出现的状态有 n!个，则描述 n个记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为
28、2 h-1 ；反之，若有 u个叶子结点，则二叉树的高度至少为(log 2 u)+1。这就是说，描述 n个记录排序的判定树必定存在一条长度为 log 2 (n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是 log 2 (n!)。根据斯特林公式，有 log 2 (n!)=O(nlog 2 n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为 O(nlog 2 n)。)解析：已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?（分数：8.00）(1).关
29、键字自小到大有序(key 1 kye 2 key n )；（分数：2.00）_正确答案：(正确答案：本题主要考查直接插入法的算法思想及性能分析。 根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。 在关键字自小到大有序的情况下，插入第 i个(2in)元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n1。)解析：(2).关键字自大到小逆序(key 1 key 2 key n )；（分数：2.00）_正确答案：(正确答案：在关键字自大到小有序的情况下，插入第 i个(2in)元素的比较次数为 i，因此，总的比较次数为 2+3+4+n=n(n+1)2一 1=(n1)(n+2)2。
30、)解析：(3).奇数关键字顺序有序，偶数关键字顺序有序(key 1 key 3 ，key 2 key 4 )；（分数：2.00）_正确答案：(正确答案：在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为 n一 1。)解析：(4).前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1 key 2 key m ，key m+1 key m+2 key n ，m 为中间位置)。（分数：2.00）_正确答案：(正确答案：在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的
31、关键字较次数最少，此时前半部分的比较次数为 m一 1，后半部分的比较次数为(n 一 m一 1)(nm+2)2，因此，总的比较次数为 m一 1+(n一 m一 1)(n一 m，m+2)2=(n-1)(n+8)8(假设 n为偶数，m=n2)。)解析：对于 n个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n个元素的初始排序有关。问：（分数：8.00）(1).当 n=7时，在最好情况下需进行多少次比较?请说明理由。（分数：2.00）_正确答案：(正确答案：在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度 n=2k一 1，那么第一遍划分得到两个长度均为n2的子文件，第二遍划分得
32、到 4个长度均为n4的子文件，以此类推，总共进行 k=log 2 (n+1)遍划分，各子文件的长度均为 1，排序完毕。当 n=7时，k=3，在最好情况下，第一遍需比较 6次，第二遍分别对两个子文件(长度均为 3，k=2)进行排序，各需 2次，共 10次即可。)解析：(2).当 n=7时，给出一个最好情况的初始排序的实例。（分数：2.00）_正确答案：(正确答案：在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。)解析：(3).当 n=7时，在最坏情况下需进行多少次比较?请说明理由。（分数：2.00）_正确答案：(正确答案：在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最
33、小值)，那么只能得到左(或右)子文件，其长度比原长度少 1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为 O(n 2 )。所以当 n=7时，最坏情况下的比较次数为 21次。)解析：(4).当 n=7时，给出一个最坏情况的初始排序的实例。（分数：2.00）_正确答案：(正确答案：在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。)解析：关于堆的一些问题：（分数：6.00）(1).堆的存储表示是顺序的，还是链接的?（分数：2.00）_正确答案：(正确答案：堆的存储是顺序的。)解析：(2).设有一
34、个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?（分数：2.00）_正确答案：(正确答案：最大值元素一定是叶子结点，在最下两层上。)解析：(3).对 n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 O表示法)?（分数：2.00）_正确答案：(正确答案：在建含有 n个元素、深度为 h的堆时，其比较次数不超过 4n，推导如下： 由于第 i层上的结点数至多是 2 i-1 ，以它为根的二叉树的深度为 h-i+1，则调用n2次筛选算法时总共进行的关键字比较次数不超过下式之值： )解析：解析：此题考查的知识点是堆的基本定义及效率。堆定义为 n
35、个关键字序列 K 1 ，K 2 ，K n ，当且仅当该序列满足如下性质(简称为堆性质)： (1)k i K 2 ，且 k i K 2i+1 或 (2)k i K 2 ；且 k i K 2i+1 (1in)。k i 相当于二叉树的非叶结点，K 2i 则是左孩子，k 2i+1 是右孩子。22.若有 N个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 ，请用文字简要说明如何在 log 2 n的时间内将其重新调整为一个堆。（分数：2.00）_正确答案：(正确答案：K 1 K n 是堆，在 K n+1 加入后，将 K 1 K n+1 调成堆。设 c=n+1，f=c2，若 K f K c ，则调
36、整完成。否则 K f 与 K c 交换之后，c=f，f=c2，继续比较，直到 K f K c ，或 f=0，即为根结点，调整结束。)解析：23.冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。（分数：2.00）_正确答案：(正确答案：void BubbleSort2(int a，int n) 相邻两趟向相反方向起泡的冒泡排序算法 int change=1；low=0；high=n1； 冒泡的上下界 while(lowai+1)ai+ai+1；change=1；有交换，修改标志 change high-； 修改上界 fo
37、r(i=high；ilow；i 一一) 从下向上起泡 if(ai解析：24.有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。 设计实现计数排序的算法。对于有 n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?（分数：2.00）_正确答案：(正确答案：typedef struct int key： datatype info RecType； void CountSort(RecT)，pe a，b，int n) 计数排序算法，将 a中记录排序放入 b中 int i，j，cnt； for(i=0；i 2次。 简单选择排序算法比本算法好。简单选择排序的比较次数是 n(n-1)
