首页 > 试题广场 >

某线性表中有100000个元素,其中前99990个元素递增有

[单选题]
某线性表中有100000个元素,其中前99990个元素递增有序,则采用()方法进行递增排序时关键字比较次数最少。
  • 简单选择排序
  • 直接插入排序
  • 二路归并排序
  • 快速排序
推荐
B。考察的是排序原理和适用场景
根据题目中的“前99990个元素递增有序”,得出关键字比较次数最少的原理就是这99990个元素不参与比较或者移动等耗时操作。
根据以下对各种排序的思想分析,二路归并和快速排序没有利用大部分为递增序列而不参与比较或者移动的操作,简单排序的时间复杂度大于直接插入排序。所以选B。
  • 简单选择排序思想为在当前待排序数列中选出最小值添加到有序序列中,其移动次数正序为0次,比较次数复杂度O(n2)
  • 直接插入排序思想为整个排序过程为n-1趟,先将序列中的第一个当成有序子序列,然后从第二个开始逐个进行插入,直至整个序列有序,最好的情况下正序移动次数为0,比较次数为n-1,时间复杂度为O(n)
  • 二路归并排序初始序列含有n个记录则可以看成n个有序的子序列,每个子序列长度为1;两两合并,得到n/2个长度为2或1的有序子序列,再两两合并,……如此重复,直到得到一个长度为n的有序序列为止。归并时间复杂度O(nlog2n)
  • 快速排序选定一个基准值,通过一趟排序将待排分割成独立的两部分,前一部分均小于或等于基准值,后一部分大于基准值,然后对每个部分继续进行上述的重复操作,直到整个序列有序。最好的情况是基准值能够均衡分为两部分,最坏的就是只得到一个比上一次划分少一个记录的子序列O(n2)
编辑于 2020-01-21 15:48:51 回复(0)
直接插入排序:分两部分,一部分有序,一部分无序。相当于前面99990是有序的,后面部分是无序的,将无序部分进行有序化就更好符合插入排序的思想。
发表于 2020-05-26 10:20:23 回复(0)
B
A项,简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数总是N (N - 1) / 2。简单排序的时间复杂度为 O(N*2)。因此A项错误。
B项,整体数据已经基本有序,在这种情形下直接插入排序执行效率最好,前99990个元素每次插入都不用移动前面的元素,时间复杂度为O(N)。后面10个元素对总体复杂度影响较小。因此B项正确。
C项,二路归并排序平均时间复杂度O( nlogn )。
D项,快速排序在序列基本有序时此算法性能最差。因此D项错误。
综上本题选B。
发表于 2020-01-14 17:32:05 回复(1)
直接插入排序,一部分有序,一部分无序。
发表于 2022-01-23 15:38:13 回复(0)