2. 计算机
  3. 用插入排序和归并排序算法对数组i进行从小到大排序，则分别需要进行( )次数组元素之间的比较。

用插入排序和归并排序算法对数组i进行从小到大排序，则分别需要进行( )次数组元素之间的比较。

admin2017-08-31  38
问题 用插入排序和归并排序算法对数组<3，1，4，1，5，9，6，5>i进行从小到大排序，则分别需要进行(    )次数组元素之间的比较。
选项 A、12，14
B、10，14
C、12，16
D、10，16
答案A
解析 插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。用插入排序对数组<3，1，4，1，5，9，6，5>进行排序的过程为：
    原元素序列：  监视哨  (3)，1，4，1，5，9，6，5
    第一趟排序：  3(1，3)，4，1，5，9，6，5 3插入时与l比较1次
    第二趟排序：  4(1，3，4)，1，5，9，6，5 4插入时与3比较1次
    第三趟排序：  1(1，1，3，4)，5，9，6，5 1插入时比较3次
    第四趟排序：  5(1，1，3，4，5)，9，6，5 5插入时与4比较1次
    第五趟排序：  9(1，1，3，4，5，9)，6，5 9插入时与5比较1次
    第六趟排序：  6(1，1，3，4，5，6，9)，5 6插入时与9和5分别比较1次
    第七趟排序：  5(1，1，3，4，5，5，6，9)5插入时与9，6，5分别比较1次
    因此整个排序过程需要比较的次数为12次。
    归并排序的思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。那么用归并排序对数组<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比较一次
    所以整个排序过程需要比较的次数为14次。
转载请注明原文地址:https://kaotiyun.com/show/WNRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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