首页 > 试题广场 >

如表r有100000个元素,前99999个元素递增有序,则采

[单选题]
如表r有100000个元素,前99999个元素递增有序,则采用(        )方法比较次数较少。
  • 折半插入排序
  • 冒泡排序
  • 归并排序
  • 基数排序
个人观点应该选择折半插入排序吧。
发表于 2017-06-26 17:29:42 回复(0)
更多回答
在数据近乎有序的情况下,插入排序时间复杂度低
发表于 2017-10-01 23:22:27 回复(0)
元素已有序时,插入排序的时间复杂度为O(n)
发表于 2017-06-26 16:35:12 回复(4)
折半插入排序的比较次数约为O(nlog2n),该比较次数与待排序表的初始状态无关,仅与元素个数n有关。
若是直接插入排序,比较次数为:99998(第一个元素不比较,后面99998个元素分别比较一次)+99999(最差情况)=199997次。
若是冒泡排序(带flag),最好比较次数为:99999(已经排序好了)+99998(根据flag退出)=199997次。
最坏比较次数为:99999*100000/2=好大的数(此时对应最后一个数最小)。
归并排序:共需进行O(log2n)趟排序,每趟最差比较次数反正比n小一点。。。。
发表于 2017-09-17 22:38:20 回复(0)
有序两个字注意了,敲黑板!
发表于 2019-05-09 23:05:37 回复(0)
在本身已经有序的表中进行插入排序时,可以利用折半查找到待排元素的插入位置,而折半查找的比较次数相对较少。
发表于 2019-04-16 10:39:27 回复(0)
我一直很不理解 一直会出题目: 比较次数和数据初识顺序的关系

很多人等同于时间复杂度和初始序列逆序的关系,但其实两者有区别。时间复杂度大于比较次数。(比较是时间复杂度的组成成分)

反正这个题 比较次数, 冒泡归并和序列初始顺序无关,(时间复杂度也是!),但是插排或者折半 时间复杂度和比较次数都是有关系的,
直接插排比较次数减少了很多,时间复杂度也相应降低了很多。

基数排序,不是基于比较的,(虽然它暗含了比较)。
发表于 2018-06-27 17:48:26 回复(0)
问题中要求比较次数较少的,那基数排序不是基于比较排序,岂不是比较次数最少?求解答
发表于 2017-08-14 14:00:39 回复(3)