🏷️ 知识点：排序算法
选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是（ ）。
Ⅰ.数据的规模 Ⅱ.数据的存储方式 Ⅲ.算法的稳定性 Ⅳ.数据的初始状态
A. 仅Ⅲ B. 仅Ⅰ、Ⅱ C. 仅Ⅱ、Ⅲ、Ⅳ D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
[tag_link]
正确答案：D
当数据规模较小时可选择是复杂度为O(n2)的简单排序算法，当数据规模较大时应选择复杂度为O(nlog2 n)的排序方法，当数据规模大到内存无法放下时需选择外部排序方法，Ⅰ 正确。数据的存储方式主要分为顺序存储和链式存储，有些排序方法（如堆排序）只能用于顺序存储方式，Ⅱ 正确。若对数据稳定性有要求，则不能选择不稳定的排序方法，Ⅲ 显然正确。当数据初始基本有序时，直接插入排序的效率最高，冒泡排序和直接插入排序的时间复杂度都是O(n)，而归并排序的时间复杂度依旧是O(nlog2 n)，Ⅳ 正确。所以选 D。
排序趟数与序列的原始状态有关的排序方法是（ ）。
A. 插入排序 B. 选择排序 C. 冒泡排序 D. 快速排序
[tag_link]
正确答案：C
排序算法的趟数通常指完成排序所需的全过程遍历次数。 对于选项中的几种排序方法：插入排序和选择排序的趟数都是固定的，与序列的原始状态无关。 插入排序需要 n-1 趟将每个元素插入已排序部分，选择排序也需要 n-1 趟选择最小元素，它们的趟数仅由元素个数决定。
冒泡排序的趟数则与序列的原始状态密切相关。 在优化后的冒泡排序中，每一趟遍历比较相邻元素，如果某一趟没有发生任何交换，说明序列已经有序，排序可以提前结束。 因此，在最好情况下（序列已有序），只需一趟即可完成； 在最坏情况下（序列逆序），需要 n-1 趟。 这使得趟数直接受原始序列顺序影响。
快速排序的性能虽与原始状态有关，但“排序趟数”并非其标准描述方式，它更侧重于递归深度或划分次数，这些虽与原始状态相关，但概念上不如冒泡排序的趟数明确。 因此，本题中排序趟数与序列原始状态有关的方法是冒泡排序。
下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是（）。
A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序
[tag_link] 正确答案：C 基数排序 的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的初始排列明显相关的。
现有 n 名学生的成绩记录，每位学生的记录包含两门课程的成绩：课程 1（记为C1）和课程 2（记为C2）。排序规则如下：
- 首先，依据C1成绩升序排列；
- 若两名学生的C1成绩相同，则依据其总分（即C1+C2）升序排列。请从下列排序算法中，选择最适合实现上述需求的算法（ ）
A. 基数排序 B. 快速排序 C. 希尔排序 D. 选择排序
[tag_link]
正确答案：A
排序规则要求先按 C1 成绩升序，再按总分升序，这属于多键排序问题。基数排序是一种稳定的排序算法，特别适合多键排序，因为它可以对每个键位进行独立排序，且稳定性保证了当主键（C1）相同时，次键（总分）的顺序得以保持。具体实现时，可以先按总分（低优先级键）进行稳定排序，再按 C1（高优先级键）进行稳定排序，从而满足规则。其他算法中，快速排序、希尔排序和选择排序都不是稳定的，虽然可以通过自定义比较函数在一次排序中处理多键，但稳定性和效率不如基数排序。此外，学生成绩通常为整数，基数排序对整数排序效率较高。因此，基数排序是最适合的算法。
数据序列（2,1,4,9,8,10,6,20）只能是（ ）排序的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
[tag_link]
正确答案：A
首先分析序列（2,1,4,9,8,10,6,20）作为各排序算法两趟后的可能性。 冒泡排序两趟后，最大和第二大元素应位于末尾，但序列末尾为 6 和 20，第二大的 10 不在倒数第二，排除 B。 选择排序两趟后，最小和第二小元素应位于前两位，但序列前两位为 2 和 1，而非 1 和 2，排除 C。 插入排序两趟后，前两个元素应有序，但序列前两位为 2 和 1（无序），排除 D。
快速排序的可能在于：序列中元素 4 满足左边（2,1）均小于 4，右边（9,8,10,6,20）均大于 4，符合快速排序一趟分区后枢轴就位的特征。 考虑两趟操作：第一趟以最后一个元素 20 为枢轴进行分区，由于 20 最大，分区后序列不变； 第二趟对左子序列（2,1,4,9,8,10,6）以 4 为枢轴进行分区，使 4 就位，且左子序列保持为 2,1,4,9,8,10,6，从而得到当前序列。 尽管枢轴选择可能非标准（如选中间元素），但快速排序允许不同策略，而其他算法均不匹配，因此 A 正确。
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是()。
A. 递归次数与初始数据的排列次序无关。 B. 每次划分后，先处理较长的分区可以减少递归次数。 C. 每次划分后，先处理较短的分区可以减少递归次数。 D. 递归次数与每次划分后得到的分区的处理顺序无关。
[tag_link]
正确答案：D
快速排序 的递归次数与元素的初始排列有关。
若每次划分后分区比较平衡，则递归次数少；
若划分后分区不平衡，则递归次数多。
但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并 不会影响树中的分支数。
为实现快速排序算法，待排序序列宜采用的存储方式是（）
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
[tag_link]
正确答案：A
对绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ．简单选择排序
Ⅱ．希尔排序
Ⅲ．快速排序
Ⅳ．堆排序
Ⅴ．二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅲ、Ⅴ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
[tag_link]
正确答案：A本题考察不同 内部排序 算法的细节：
- 对于 I，简单选择排序每次选择未排序列中的最小元素放入其最终位置。
- 对于 II，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。
- 对于 III，快速排序每一趟排序结束后都将枢轴元素放到最终位置。
- 对于 IV，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。
- 对于 V，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。I、III、IV 正确，本题选择 A。
用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15,则该趟排 序采用的增量(间隔)可能是()。
A.2
B.3
C.4
D.5
[tag_link]
正确答案：B
首先，第二个元素为 1，是整个序列中的最小元素，所以可知该 希尔排序 为从小到大排序然后考虑增量问题，若增量为 2，第 1+2 个元素 4 明显比第 1 个元素 9 要大，A 排除；若增量为 3，第 i、i+3、i+6 个元素都为有序序列 (i=1,2,3)，符合希尔排序的定义；若增量为 4，第 1 个元素 9 比第 1+4 个元素 7 要大，C 排除；若增量为 5，第 1 个元素 9 比第 1+5 个元素 8 要大，D 排除，选 B。
在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（）
Ⅰ. 归并排序的程序代码更短Ⅱ. 归并排序的占用空间更少Ⅲ. 归并排序的运行效率更高
A. 仅 Ⅱ B. 仅 Ⅲ C. 仅 Ⅰ、Ⅱ D. 仅 Ⅰ、Ⅲ
[tag_link]
正确答案：B
参考 排序算法复杂度 ，归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n), 后者是O(1)。但是前者时间复杂度是O(nlogn), 后者是O(n2)。所以 B 正确。
对初始数据序列 (8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6) 进行希尔排序。若第一趟排序结果为 (1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)，第二趟排序结果为 (1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)，则两趟排序采用的增量（间隔）依次是（ ）。
A. 3,1 B. 3,2 C. 5,2 D. 5,3
[tag_link]
正确答案：D
参考 希尔排序 ，可以观察到，第一次排序后的数组沿 gap=5 有序，第二次排序后数组沿 gap=3 有序，所以答案选择 D。
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（ ）。
A. 5，2，16，12，28，60，32，72 B. 2，16，5，28，12，60，32，72 C. 2，12，16，5，28，32，72，60 D. 5，2，12，28，16，32，72，60
[tag_link]
正确答案：D
快速排序每趟都将基准元素放在其最终位置，然后以它为基准将序列划分为两个子序列，基准左边都比基准小，右边都比基准大。排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”，故快速排序第一趟被枢轴分成的 两个子序列 在第二趟中应该 各放一个枢轴 在最终位置（也即如果第一趟的枢轴在中间，第二趟应该至少有 3 个元素在最终位置），如果枢轴的位置正好在首端或尾端，那第一趟就只被分成了 一个序列，那第二趟只能放 一个枢轴 在最终位置（也即如果枢轴在首尾，第二趟应该至少有 2 个元素在最终位置）
- A 中，第一次快排选的基准值是 72，第二次的基准值是 28。
- B 中，第一次的基准值是 72，第二次的是 2。
- C 中，第一次的基准值是 28，第二次的基准值是 2 和 32。所以答案选择 D。
设数组 S[] = {93, 946, 372, 9, 146,151, 301, 485, 236, 327, 43, 892}, 采用最低位优先（LSD）基数排序将 S 排列成升序序列。第 1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是 ( )
A. 43,892 B. 236,301 C. 301,892 D. 485,301
[tag_link]
正确答案：C
LSD 基数排序 第一趟根据最低位对数组进行排序，得到的结果为 {151, 301, 372, 892, 93, 43, 485, 946, 146, 267, 327}。
下列排序算法中，不稳定的是（ ）
I. 希尔排序
II. 归并排序
III. 快速排序
IV. 堆排序
V. 基数排序
A. 仅 I 和 II B. 仅 II 和 V C. 仅 I，III，IV D. 仅 III，IV，V
[tag_link]
正确答案：C
参考 排序总结 ，快速排序在每一轮划分时，通常选择一个枢轴元素将序列分成两部分，并且在交换 元素时可能改变相同关键字元素的相对顺序，因此不是稳定的排序算法。堆排序使用堆数据 结构进行排序，其中在建堆和调整堆的过程中，元素的交换可能导致相同关键字元素的相对 顺序发生改变，因此堆排序也不是稳定的排序算法。希尔排序是基于插入排序的一种改进算 法，它通过将待排序的序列划分成若干个较小的子序列进行插入排序，然后逐步缩小子序列 的间隔，最终完成整个序列的排序。由于希尔排序是通过跳跃式的插入排序进行排序的，相 同关键字的元素可能会跨越较大的间隔进行比较和交换。这种跨越较大间隔的比较和交换可 能导致相同关键字的元素的相对顺序发生改变，因此希尔排序是不稳定的排序算法。因此不 稳定的排序算法有希尔排序、快速排序、堆排序。本题答案选 C。
下列排序算法中，最坏情况下元素移动最少的是（ ）。
A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 简单选择排序
[tag_link]
正确答案：D
排序算法的元素移动次数参考 此节 ，其中简单选择排序迭代 n 轮，每次确定一个元素的最终位置，元素移动次数平均为O(n)。
如果一台计算机具有多个可以并行运行的 CPU，就可以同时执行相互独立的任务，则下列排序算法中，适合并行处理的是（ ）。
A. II、VI 和 V
B. II、III 和 V
C. II、III、IV 和 V
D. I、II、III、IV 和 V
[tag_link]
正确答案：A
考查各种排序算法的性质。 本题即分析排序算法的执行过程中，能否划分成多个子序列进行并行独立的排序。 快速排序在一趟排序划分成两个子序列后，各子序列又可并行排序； 归并排序的各个归并段可以并行排序。 而希尔排序分出来的几组子表也可以进行相对独立的排序。 因此 II、VI 和 V 满足并行性。 而其他选项不能划分成子序列来并行执行排序，故选 A。
对 {05,46,13,55,94,17,42} 进行基数排序，一趟排序的结果是（ ）。
A. 05,46,13,55,94,17,42
B. 05,13,17,42,46,55,94
C. 42,13,94,05,55,46,17
D. 05,13,46,55,17,42,94
[tag_link]
正确答案：C
基数排序通常从最低有效位（LSD）开始，对数字的每一位进行稳定排序。 给定序列 {05,46,13,55,94,17,42} 均为两位数，第一趟排序根据个位数字进行。 首先，提取每个数字的个位：05（个位 5）、46（个位 6）、13（个位 3）、55（个位 5）、94（个位 4）、17（个位 7）、42（个位 2）。 按照个位数字分配桶（0-9），保持稳定性： 个位 2:42 个位 3:13 个位 4:94 个位 5:05、55（保持原序，05 在 55 前） 个位 6:46 个位 7:17 按桶顺序收集数字，得到序列：42,13,94,05,55,46,17。 这与选项 C 一致。 选项 A 是原始序列； 选项 B 是完全排序后的结果； 选项 D 不符合个位排序顺序。 因此，一趟排序结果为 C。
对一组数据(2,12,16,88,5,10)进行排序，若前三趟排序结果如下：
第 一 趟排序结果：2,12,16,5,10,88
第二趟排序结果：2,12,5,10,16,88
第三趟排序结果： 2,5,10,12,16, 88
则采用的排序方法可能是()。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序
[tag_link]
正确答案：A
本题考查 内部排序 的特征，题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值“沉底”，符合冒泡排序的特点。
看第一趟可知仅有 88 被移到最后。
如果是希尔排序，则 12,88,10 应变为 10,12,88。
因此排除希尔排序。
如果是归并排序，则长度为 2 的子序列是有序的。
因此可排除归并排序。
如果是基数排序，则 16,5,10 应变为 10,5,16。
因此排除基数排序。
提示：对于此类题，先看备选项的排序算法有什么特征，再看题目中的排序过程是否符合这一特征，从而得出答案。
一般先从选项中的简单排序方法（插入排序、起泡排序、选择排序）开始判断，若简单排序方法不符合，再判断排序方法（希尔排序、快速排序、堆排序、归并排序）。
对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
[tag_link]
正确答案：D
本题考察 插入排序 ，折半插入排序与直接插入排序是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数n，两者都是n−1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为O(nlog2n)：直接插入排序的比较次数与序列初态有关，为O(n)∼O(n2)。
对给定的关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分配收集后得到的关键字序列是（）。
A.007，110，119，114，911，120，122
B.007，110，119，114，911，122，120
C.007，110，911，114，119，120，122
D.110，120，911，122，114，007，119
[tag_link] 正确答案：C基数排序 一般使用低位优先，即第 1 趟排序是按照个位数字的大小来排序的，第 2 趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。
下列选项中，不可能是快速排序第2趟排序结果的是()。
A.2,3,5,4,6,7,9
B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9
D.4,2,3,5,7,6,9
[tag_link]
正确答案：C
快速排序 的阶段性排序结果的特点是，第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。
题目问第二趟 排序的结果，即要找不存在两个这样的数的选项。
A 选项中 2、3、6、7、9 均符合，所以 A 排除；
B 选项中，2、9 均符合，所以 B 排除；
D 选项中 5、9 均符合，所以 D 选项排除；
最后看 C 选项，只有 9 一个数符合，所以 C 不可能是快速排序第二趟的结果。
组成原理 12 程序 P 在机器 M 上的执行时间是 20 秒，编译优化后，P 执行的指令数减少到原来的 70%，而 CPI 增加到原来的 1.2 倍，则 P 在 M 上的执行时间是（ ）。
计算机性能指标 A. 8.4 秒 B. 11.7 秒 C. 14 秒 D. 16.8 秒 查看答案与解析 收藏 正确答案： 不妨设原来指令条数为 X，那么原 CPI 就为 20/x，经过编译优化后，指令条数减少到原来的 70%，即指令条数为 0.7x，而 CPI 增加到原来的 1.2 倍，即 24/x，那么 现在 P 在 M 上的执行时间就为 指令条数×CPI = 0.7x × 24/x = 24x0.7 = 16.8s，选 D。
希尔排序的组内排序采用的是（）。
A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 归并排序
[tag_link] 正确答案：A 希尔排序 的思想是：先将待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）
Ⅰ. 插入排序 Ⅱ. 选择排序 Ⅲ. 起泡排序 Ⅳ. 希尔排序 Ⅴ. 堆排序
A. 仅 Ⅰ、Ⅱ B. 仅 Ⅱ、Ⅲ C. 仅 Ⅲ、Ⅳ D. 仅 Ⅳ、Ⅴ
[tag_link]
正确答案：D
插入排序、选择排序、冒泡原本时间复杂度是O(n2)，更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选 D。
对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是（ ）。
I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需要的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少
A. 仅 I B. 仅 III C. 仅 I，II D. 仅 I，II 和 III
[tag_link]
正确答案：A
考虑较极端的情况，对于有序数组， 直接插入排序 的比较次数为n−1，简单选择排序的比较次数始终为1+2+⋯+n−1=n(n−1)/2，I 正确。两种排序方法的辅助空间都是O(1)，无差别，II 错误。初始有序时，移动次数均为 0；对于通常情况，直接插入排序每趟插入都 需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，III 错误。
对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是()。
I. 大部分元素已有序
II 待排序元素数量很少
Ⅲ.要求空间复杂度为 O(1)
IV. 要求排序算法是稳定的
A. 仅 I 、Ⅱ
B. 仅Ⅲ、IV
C. 仅 I 、Ⅱ 、IV D.I 、II 、ⅢI 、IV
[tag_link]
正确答案：D
直接插入排序 和 快速排序 的特点如下表所示：
| 排序算法 | 适合初始序列情况 | 适合元素数量 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 直接插入排序 | 大部分元素有序 | 较少 | O(1) | 稳定 |
| 快速排序 | 基本无序 | 较多 | O(log₂n) | 不稳定 |
I. 大部分元素已有序 ✅ 正确。
直接插入排序在序列 基本有序 的情况下表现非常好，接近 O(n) 的时间复杂度，而快速排序在此场景下仍需要递归处理。
因此此项成立。
II. 待排序元素数量很少 ✅ 正确。
当元素数量较少时，插入排序的常数因子小、实现简单， 实际运行效率往往优于快速排序 ，这是实际工程中的常见优化策略（如许多库排序在小规模时使用插入排序）。
III. 要求空间复杂度为 O(1) ✅ 正确。
插入排序是 原地排序 ，空间复杂度为 O(1)；
而快速排序虽然通常也是原地排序，但某些实现（尤其是递归调用）存在 O(log n) 的栈空间。
若对空间要求极严，插入排序更适合。
IV. 要求排序算法是稳定的 ✅ 正确。
插入排序是 稳定排序 ，而快速排序是 不稳定的 （原始版本）。
如果应用场景要求排序后相等元素的相对顺序不变，选择插入排序是合理的。
综上，所有说法都正确，正确答案选择 D。
组成原理 12 某计算机主频为 1GHz，程序 P 运行过程中，共执行了 10000 条指令，其中，80% 的指令执行平均需 1 个时钟周期，20% 的指令执行平均需 10 个时钟周期。
程序 P 的平均 CPI 和 CPU 执行时间分别是（ ）。
计算机性能指标 A. 2.8，28μs B. 28，28μs C. 2.8，28ms D. 28，28ms 查看答案与解析 收藏 正确答案： 参考 指令执行指标 ，CPI 指平均每条指令的执行需要多少个时钟周期。
由于 80% 的指令执行平均需要 1 个时钟周期，20% 的指令执行平均需要 10 个时钟周期，因此 CPI = 80% × 1 + 20% × 10 = 2.8 。
计算机主频为 1GHz，程序 P 共执行 10000 条指令，平均每条指令需要 2.8 个时钟周期，因此， CPU 执行时间= ( 10000 × 2.8 ) /1 0 9 = 2.8 × 1 0 − 5 s = 28 μ s 。
使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢（ ）。
A. 11 B. 70 C. 80 D. 81
[tag_link]
正确答案：D
在 快速排序 中，划分过程通常选择一个枢轴元素来将待排序序列划分为两个子序列。因为是升序排序，所以枢纽元素的前半个子序列的值需要都小于枢轴值，后半个子序列的值需要都大于枢轴值。分别从每个选项来看，A 选项的枢轴值为 11，前半个子序列的值只有68，大于枢轴值 11，不符合。B 选项的枢轴值为 70，前半个子序列都小于 70，但后半个子序列存在 23 和 48 小于 70，不符合。C 选项的枢轴值为 80，前半个子序列的值都小于 80，但是后半个子序列存在 48 小于 80，不符合。D 选项的枢轴值为 81，81 前面的元素都小于 81，81 后面的元素都大于 81，符合。因此本题的正确选项为 D。
对含 9 个关键字的初始序列进行排序，若序列的变化情况如下表所示，则下列排序算法中，采用的是（ ）。
| 初始序列 | 5, 25, 40, 30, 10, 20, 45, 15, 35 |
|---|---|
| 第 1 趟排序后的序列 | 5, 10, 20, 30, 15, 35, 45, 25, 40 |
| 第 2 趟排序后的序列 | 5, 10, 15, 25, 20, 30, 40, 35, 45 |
A. 希尔排序 B. 基数排序 C. 归并排序 D. 折半插入排序
[tag_link]
正确答案：A
第一次排序后，下标相差 3 的子序列有序。第二次排序后，下标相差 2 的子序列有序。由此判断是 希尔排序 。
已知某排序算法如下：
void cmpCountSort(int a[], int b[], int n)
{
int i, j, *count;
count = (int *) malloc(sizeof(int) * n) //C++ 语言：count = new int[n];
for (i = 0; i < n; i++) count[i] = 0;
for (i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (a[i] < a[j]) count[j]++;
else count[i]++;
for (i = 0; i < n; i++) b[count[i]]= a[i];
free(count); // C++ 语言：delete count;
}
请回答下列问题。
(1) 若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6]; ，则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么？
(2) 若 a 中含有 n 个元素，则算法执行过程中，元素之间的比较次数是多少？
(3) 该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。
[tag_link]
cmpCountSort 算法基于计数排序的思想，对序列进行排序。cmpCountSort 算法遍历数组中的元素，count 数组记录比对应待排序数组元素下标大的元素个数，例如，count[1]=3的意思是数组 a 中有 3 个元素比 a[1]大，即 a[1]是第 4 大元素，a[1]的正确位置应是 b[3]。
1）排序结果为 b[6]={-10,10,11,19,25,25}。
2）由代码 for(i=0;i<n-1;i++) 和 for(j=i+1;j<n;j++) 可知，在循环过程中，每个元素都与它后面的所有元素比较一次（即所有元素都两两比较一次），比较次数之和为(n−1)+(n−2)+⋯+1，故总的比较次数是n(n−1)/2。
3）不是。需要将程序中的 if 语句修改如下：
if(a[i]<=a[j]) count[j]++;
else count[i]++;
如果不加等号，两个相等的元素比较时，前面元素的 count 值会加 1，导致原序列中靠前的元素在排序后的序列中处于靠后的位置。