首页 > 试题广场 >

设 一组初始记录关键字序列为(50，40，95，20，15，

[单选题]

设 一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。 

  • 40，50，20，95
  • 15，40，60，20
  • 15，20，40，45
  • 45，40，15，20
查看正确选项
添加回答
屈服于现实的三岁多一点的孩子头像 屈服于现实的三岁多一点的孩子
希尔排序属于插入类排序，是将整个有序序列分割成若干小的子序列分别进行插入排序。
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di = 1，即所有记录放进一个组中排序为止。
题目中：d = 4，排序之后为：15,40,60,20,50,70,95,45
               d = 2，排序之后为：15,20,50,40,60,45,95,70
               d = 3，排序之后为：15,20,40,45,50,60,70,95
发表于 2019-04-18 13:02:26 回复(0)
我已进阿里头像 我已进阿里
希尔排序本质就是带增量的插入排序。本质意思为：先将整个待排元素序列由相隔的某个增量分割成若干个子序列分别进行直接插入排序，然后依次缩减增量再进行排序，当整个序列的元素基本有序时，再对全体的元素进行依次直接插入排序。故整个增量排序的变化过程为：
d=4:15,40,60,20,50,70,95,45
d=2:15,20,50,40,60,45,95,70
d=1:15,20,40,45,50,60,70,95
发表于 2018-04-13 14:24:25 回复(0)
nomico271头像 nomico271
一趟希尔排序后结果为：15 40 60 20 50 70 95 45
发表于 2017-07-14 12:51:43 回复(2)
程序猿Go师傅头像 程序猿Go师傅
增量d=4，

于是序列50，40，95，20，15，70，60，45中，50，15是一组，40，70是一组，95，60是一组，20，45是一组

经过组内排序后变为：【15，50】 【40，70】【60，95】【20，45】，于是答案为15,40,60,20
发表于 2020-03-01 21:28:20 回复(0)
快到碗里来23333头像 快到碗里来23333
已知步长为4
排序前：
50 40 95 20
15 70 60 45
排序后:
15 40 60 20
50 70 95 45
发表于 2017-11-17 12:12:48 回复(0)
道小理头像 道小理
根据希尔排序的算法思想，以增量d=4进行一趟排序，相当于将待排序序列分成了4个子序列，每个子序列中的元素下标对d取余结果相同。对于本题中的初始记录关键字序列，以d=4为增量时，可以得到以下4个子序列：


[50, 15]
[40, 70]
[95, 60]
[20, 45]


对每个子序列进行插入排序，排序后可以得到以下子序列：


[15, 50]
[40, 70]
[60, 95]
[20, 45]


因此，以增量d=4进行一趟排序后，前4条记录关键字依次为15、40、60和20。
编辑于 2023-05-04 09:20:26 回复(0)
提交观点

问题信息

排序
上传者：阿奻_
难度：
6条回答 11868浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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