我要招人

去企业版

首页 > 试题广场 >

对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间

[单选题]

对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。

```
排序的总趟数
```
```
元素的移动次数
```
```
使用辅助空间的数量
```
```
元素之间的比较次数
```

查看正确选项

牛客5651581号

折半插入排序基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同，折半插入排序采用折半查找法来寻找插入位置。

发表于 2017-07-17 17:57:38 回复(0)

紫旋

折半插入排序，是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。所以，很明显比较的次数减少了。

发表于 2017-01-02 08:40:37 回复(4)

侯卿

关于与数组初始状态无关的排序算法：

1、算法复杂度与初始状态无关；

2、元素总比较次数与初始状态无关；

3、元素总移动次数与初始状态无关。

4、排序趟数与初始状态无关

具体分析参见博客：http://www.cnblogs.com/Xieyang-blog/p/8340578.html

发表于 2018-03-03 15:38:50 回复(0)

嘿哈嘿

可能有的小伙伴认为移动次数也变少了，解释一下:比如1，2，4，5，现在3***去，那4，5都得向后移一位才行，和直接插入排序是一样的移动次数

发表于 2018-12-02 17:31:17 回复(0)

大桔骑士v

折半插入排序 = 利用折半查找找插入点的插入排序

所以原来这个排序过程是怎么排的，现在这个过程还是怎么排的（因此ABC不变），只是说找插入点的速度变快了（所以D比较次数变少了）。

发表于 2020-05-10 19:23:33 回复(0)

谟叶

移动次数应该也不一样呀

发表于 2017-11-23 14:12:17 回复(1)

Juventus-小九

选基算法中比较次数与初始元素序列排序无关

发表于 2022-01-19 21:41:44 回复(0)

PianoboyRichardX

我看了各位大佬的评论，如果说将待排序列看成数组，那一切都解释的通；但是，B选项，假如给定待排序列4561，折半插入排序和直接插入排序元素的移动次序就不一样了啊，直接插入排序就可以直接放在4前面，而折半插入排序则先放在5前面再进行排序，明显移动次序就不一样了。待排序列如果不是数组呢？该如何解释

发表于 2021-07-18 16:40:46 回复(0)

名字是谷雨

移动次数依赖于初始状态

发表于 2019-10-23 18:17:25 回复(0)

提交观点

问题信息

排序

上传者：城市里的养猫者

难度：

9条回答 348收藏 7820浏览

对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间

问题信息

热门推荐

相关试题