2. 从业资格
  3. 用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5>进行从小到大排序

用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5>进行从小到大排序

考试题库2022-08-02  33
问题 用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5>进行从小到大排序，则分别需要进行（　　）次数组元素之间的比较。A.12，14B.10，14C.12，16D.10，16
选项 A.12，14
B.10，14
C.12，16
D.10，16
答案 A
解析 插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。假设n个待排序元素存储在数组R[n+1]中（R[0]预留），则：
（1）初始时数组R[1..1]中只包含元素R[1]，则数组R[1..1]必定有序；
（2）从i=2到n，执行步骤3；
（3）此时，数组R被划分成两个子区间，分别是有序区间R[1..i-1]和无序区间R[i..n]，将当前无序区间的第1个记录R插入到有序区间R[1..i]中适当的位置上，使R[1..i]变为新的有序区间。
在实现的过程中，设置监视哨R[0]，并从R[i-1]到R[0]查找元素R的插入位置
那么用插入排序对数组＜3，1，4，1，5，9，6，5>进行排序的过程为：
原元素序列：监视哨（3），1，4，1，5，9，6，5
第一趟排序：1（1，3），4，1，5，9，6，51插入时与3比较1次
第二趟排序：4（1，3，4），1，5，9，6，54插入时与3比较1次
第三趟排序：1（1，1，3，4），5，9，6，51插入时分别与4、3、1比较1次，共比较3次
第四趟排序：5（1，1，3，4，5），9，6，55插入时与4比较1次
第五趟排序：9（1，1，3，4，5，9），6，59插入时与5比较1次
第六趟排序：6（1，1，3，4，5，6，9），56插入时与9和5分别比较1次，共比较2次
第七趟排序：5（1，1，3，4，5，5，6，9）5插入时与9，6，5分别比较1次，共比较3次。
那么整个排序过程需要比较的次数为12次。
归并排序的思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。其基本步骤如下：
（1）将n个元素的待排序序列中每个元素看成有序子序列，对相邻子序列两两合并，则将生成n/2个子有序序列，这些子序列中除了最后一个子序列长度可能小于2外，其他的序列长度都等于2；
（2）对上述n/2个长度为2的子序列再进行相邻子序列的两两合并，则产生n/4个子有序序列，同理，只有最后一个子序列的长度可能小于4；
（3）第i趟归并排序为，对上述n/i个长度为i的子序列两两合并，产生n/2i个长度为2i的子有序序列；
（4）重复执行此步骤，直到生成长度为n的序列为止。
那么用归并排序对数组＜3，1，4，1，5，9，6，5>进行排序的过程为：
原元素序列：3，1，4，1，5，9，6，5
第一趟排序：[1，3]，[1，4]，[5，9]，[5，6]比较4次
第二趟排序：[1，1，3，4]，[5，5，6，9]前半部分比较3次，后半部分比较3次
第三趟排序：[1，1，3，4，5，5，6，9]5分别与1，1，3，4比较一次，共比较4次，后面的序列都不小于5，因此可以直接复制到结果序列。
所以整个排序过程需要比较的次数为14次。
转载请注明原文地址:https://tihaiku.com/congyezige/2410312.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)