首页 > 试题广场 >

关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)

[填空题]
关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell的排序法，则一趟扫描的结果是1；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是2。
查看答案及解析
添加回答
霖淼书生头像 霖淼书生
希尔排序，步长默认先从数组长度的一般开始，然后每次减半，直到最后为1
题目所给为4，因此，上来1,5,9号元素（即QQR）进行比较，在这三个位置上进行排序，即还是QQR
然后2,6,10号元素（即HAD）进行比较，在这三个位置上进行排序，即变成了ADH
依次排序后面的，即可获得QACSQDFXRHMY
快排，主要看排序时，从后往前和从前往后的比较过程中，加不加等号。
以第一个元素为pivot，从后往前，遇到第一个比pivot小的，则换到前面，然后从前面开始往后遍历，遇到第一个比pivot大的则换到后面，此题答案对应的是没有等号的情况，即严格大才会换位置。
故为  FHCDQAMQRSYX
发表于 2015-08-29 20:58:35 回复(6)
丶花花头像 丶花花
过程
头指针尾指针
QHCYQAMSRDFX
头指针尾指针
FHCYQAMSRDQX
头指针尾指针
FHCDQAMSRYQX
指针相遇
FHCDMAQSRYQX

这是在数组中索引移动，左侧判断大于等于，右侧判断小于的机制 因为左侧索引移动的话必须要大于等于保持循环的一致性

发表于 2017-03-02 23:01:26 回复(3)
Recollect头像 Recollect
QACSQDFXRHMY
FHCDQAMQRSYX
发表于 2015-08-09 16:52:48 回复(0)
mirror头像 mirror
1：QACSQDFXRHMY
2：MHCFDAQSRQYX
发表于 2015-03-05 19:04:25 回复(1)
kiwiz头像 kiwiz
FHCDMAQSRYQX
发表于 2015-12-04 14:57:13 回复(0)
Un-Infinite头像 Un-Infinite
快排也有很多实现，答案不唯一才对吧。按照算法导论上的实现，顺序可以是FHCQAMDQRYSX
发表于 2015-09-05 23:00:52 回复(0)
龙崎努斯头像 龙崎努斯
有两个Q，按照《算法导论》上的做法，应该是小于等于的都放在前面，
第二个的答案应该是：FHCQAMDQRYSX
发表于 2015-09-01 16:15:44 回复(0)
Rico123头像 Rico123
第一轮希尔排序： QACSQDFXRHMF
第一轮快速排序： FHCAMDQSRYQX
发表于 2017-06-25 20:56:09 回复(0)
相信自己！头像 相信自己！
结果中加了逗号，算我全错。。。。。
发表于 2016-09-09 15:48:34 回复(0)
￥shell头像 ￥shell
第二个空的大答案不唯一吧，我想问问牛客，能不能对自己出的题目负责点，答案加个逗号就判错，第二个答案也未必是唯一的，你这样出题是在误导大家么。
发表于 2016-08-07 14:57:32 回复(0)
TheFool头像 TheFool
快排应该是FHCDQAMQRYXS吧，按照严格的大于排序，首先将轴值Q置末，最后一步应该是将l指向的S跟在末尾的轴值Q交换。
发表于 2016-04-03 13:23:20 回复(1)
win君头像 win君
醉了，写答案的时候用逗号隔开了，然后全错。。。。。。。
发表于 2016-03-16 14:32:25 回复(2)
加油呀哥们头像 加油呀哥们
第二个快排，
如果比较时没有等于的，FHCDRAMSQQYX
发表于 2015-09-03 20:09:22 回复(0)
yxliuxinglin头像 yxliuxinglin
第2个空的答案不唯一
发表于 2015-08-26 17:41:21 回复(2)
牛客8524519号头像 牛客8524519号
按照算法（第四版）的例子，感觉答案应该是：DHCFQAMQRSYX？？？
发表于 2017-03-21 21:33:39 回复(0)
飞虎头像 飞虎

第二题遇到相等，那么也要换。具体请款如下：
如这题关键字为Q,那么如果在关键字Q前面遇到字母Q，字母Q要和关键字Q互换。
个人理解，不知对否。

发表于 2017-09-10 00:23:56 回复(0)
和大胖一起越来越胖头像 和大胖一起越来越胖
每次最怕填空题，不是不会，是不知道答案是什么格式O__O "…
发表于 2017-06-07 15:40:07 回复(0)
March..头像 March..
第二个的结果依赖于具体的实现。
发表于 2017-06-02 16:33:38 回复(0)
黄小斜头像 黄小斜
希尔排序
发表于 2017-04-03 16:36:17 回复(0)
一梦了浮生头像 一梦了浮生
你妹，看上面的序列有逗号，我也加上了，悲催的错了
发表于 2016-09-14 17:30:53 回复(0)
提交观点

问题信息

腾讯 排序
来自：腾讯2014校招研发工...
难度：
33条回答 21037浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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