首页 > 试题广场 >

已知数据表A中每个元素距其最终位置不远，为节省时间排序，应采

[单选题]
已知数据表A中每个元素距其最终位置不远，为节省时间排序，应采用什么方法排序？ 
  • 堆排序
  • 直接插入排序
  • 快速排序
  • 直接选择排序
添加回答
推荐
牛客-007头像 牛客-007
答案：B
每个元素距其最终位置不远，直接插入排序不需要移动太多元素，适用于这种情况，效率高
编辑于 2015-02-03 11:15:40 回复(1)
LEE_宁心静气头像 LEE_宁心静气
“每个元素距其最终位置不远”，我个人觉得可以理解成序列相对有序

那么原题就转换成在序列相对有序的情况下，哪种排序算法的时间复杂度更小?
直接插入排序是数据越有序越快，最快时间复杂度可达到O(n) .

选择排序无论何时都是O（n^2）

快速排序越有序越慢，它要从后到前遍历找比基准小的，时间复杂度达到O(n)

发表于 2018-06-12 22:41:14 回复(0)
Ctrl+F5头像 Ctrl+F5
插入排序：如果平均每个元素离最终位置相距c个元素，则其复杂度为O(cn)，一共n趟，每次比较c次；
快速排序：最好的、平均的复杂度都是O(nlog(n))，如果每次选择的中间数都最小或最大，那就是最坏的情况，复杂度是O(n*n)；所以快速排序和元素的位置没有关系，跟选择的中间数有关。
堆排序：复杂度一直是O(nlog(n));
直接选择排序：跟元素位置没有关系，都要遍历n遍，每遍找出最小或最大数来，复杂度是O(n*n)；
答案是插入排序。

发表于 2017-03-20 09:53:53 回复(0)
龙虾姐夫头像 龙虾姐夫
选择排序也说的通啊
发表于 2016-08-25 23:54:50 回复(4)
笑以头像 笑以
有人说到选择排序也是，看看这题吧（做错了，哈哈哈）
发表于 2018-12-07 21:43:18 回复(1)
猩老师头像 猩老师
插入排序和选择排序的时间复杂度O(n^2)都来自于在遍历过程中仍然需要对序列中的一部分进行再次遍历，不过区别在于，插入排序遍历的是已经遍历过的部分，选择排序则是未遍历的部分。在接近有序的情况下，插入排序几乎可以不需要再遍历已经遍历过的部分（因为当前比较的元素大于之前遍历过的最大元素，所以不用再一个一个地和之前的对比了），时间复杂度可以降到O(n)；但选择排序无论如何都必须要一次次查看未遍历元素的最小值，时间复杂度恒定为O(n^2)
发表于 2024-09-14 10:49:40 回复(0)
你永远得不到的祖奶奶头像 你永远得不到的祖奶奶
题目中说的是：基本有序，对于选择排序来说 他需要将最小的元素挪到最前面 基本有序对他而言没什么作用，而插入排序 则是两两比较 基本有序 那么需要进行的比较次数就不会太多。
发表于 2020-05-29 10:20:05 回复(0)
不做人了头像 不做人了
打过扑克吗
发表于 2020-04-30 10:50:19 回复(0)
꧁꫞꯭꯭꯭̨̞̞̘̻̬̞C꫞꧂头像 ꧁꫞꯭꯭꯭̨̞̞̘̻̬̞C꫞꧂
希尔排序是插入排序的优化，而希尔排序的目的就是，让每个元素距其最终位置不远，这样再用插入排序的话，就会提高效率
发表于 2018-06-15 16:05:45 回复(0)
codersong头像 codersong
每个元素距离其最终位置不远就说明序列已经大致有序了，显然用插入排序节省时间
发表于 2015-10-09 20:23:25 回复(0)
听风吹的声音头像 听风吹的声音
插入排序需要移动的为插入位置以后的部分，由题意知离末尾近，所以选插入
发表于 2015-09-01 20:48:23 回复(0)
提交观点

问题信息

排序
来自：算法工程师能力评估
上传者：小小
难度：
11条回答 15180浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号