首页 > 试题广场 >

若一组记录的排序码为（46, 79, 56, 38, 40,

[单选题]

若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序，以第一个记录为基准得到的一次划分结果是 

  • 38, 40, 46, 56, 79, 84
  • 40，38, 46 ,79, 56, 84
  • 40, 38，46, 56, 79, 84
  • 40, 38，46，84, 56, 79
查看答案及解析
添加回答
wanano头像 wanano
我觉的答案是A！不知道这道题的快排方法是什么
发表于 2017-08-05 21:43:46 回复(0)
随风随缘头像 随风随缘
https://www.nowcoder.com/questionTerminal/c27fff5bcfc54e68a46879f062db776b?toCommentId=39217 参考这道题中推荐的解法，跟算法导论第三版的快排方式不一样的
发表于 2017-06-26 10:06:31 回复(0)
chestnut7头像 chestnut7

base = 46

  1. i = 0; j = 5
    此时 46, 79, 56, 38, 40, 84
    从右往左找比base小的数，如果找到，则替换i处的值
  2. i = 0; j = 4
    此时 40， 79，56，38，40，84
    从左往右找比base大的数，如果找到，则替换j处的值
  3. i = 1;j = 4
    此时 40， 79，56，38，79，84
    从右往左找比base小的数，如果找到，则替换i处的值
  4. i = 1;j = 3
    此时 40， 38，56，38，79，84
    从左往右找比base大的数，如果找到，则替换j处的值

  5. i = 2;j = 3
    此时 40， 38，56，56，79，84

  6. i=2 处填上base值46
    此时 40， 38，46，56，79，84
    选C

发表于 2018-07-25 20:25:19 回复(1)
Sones头像 Sones
AC都可以，当把46作为哨兵，快排的结果是A；当通过最右边比46小的与46交换，移到左边，再把最左边比46大的与46交换，移到右边，依次交换，最后的结果是C.
发表于 2017-08-25 13:23:42 回复(2)
bcaso头像 bcaso

初值化：基准值 base 为第一个元素的值，左指针 low 为第一个元素的值，右指针 high 为最后一个元素的值。

  • 右指针 high 找到大于 base 的值时停止左移，左指针 low 更新为 high 元素的值。
  • 左指针 low 找到小于 base 的值时停止右移，右指针 high 更新为 low 元素的值。
  • 谁更新，谁停止往对面移动，然后另一个指针移动。
  • 两指针重合的位置更新为 base 的值。

过程

base = 46

描述
low high 初始值
46 79 56 38 40 84
high high--，且找到小于 base 的值
46 79 56 38 40
low low 更新
40 79 56 38 40
low low++，且找到大于 base 的值
79 56 38 40
high high 更新
79 56 38 79
high high--，且找到小于 base 的值
79 56 38
low low 更新
38 56 38
low low++，且找到大于 base 的值
56 38
high high 更新
56 56
high high--，与 low 指针重合
56
40 38 46 56 79 84 low,high 的位置更新为 base 的值
将上面的值抄下来
编辑于 2022-12-31 10:56:49 回复(0)
曾经的板蓝根头像 曾经的板蓝根
快速排序 将基准数与最后一个元素进行交换，定义分区指示器，初始的分区指示器指向-1的位置 将每一个元素与尾部的基准数进行比较，如果小于基准数，并且分区指示器下标小于当前元素下标则交换， 如果当前元素大于基准数不交换
发表于 2019-08-06 18:18:07 回复(0)
阳光下的米雪头像 阳光下的米雪
这个题，答案有问题吧
发表于 2019-04-16 10:55:37 回复(0)
宇宙无敌小黑豆头像 宇宙无敌小黑豆
快排不是找基数吗？然后分左右这样递归
发表于 2018-05-29 20:50:48 回复(0)
尤里卡斯特头像 尤里卡斯特
第一个记录是46，也就是把46作为哨兵，然后从右边往左边遍历，遇到的第一个比46小的数是40，交换，第二个交换的比46的数是38，所以应该是先40，然后38，再46，大于46的数，顺序不变。
发表于 2018-01-29 10:52:10 回复(0)
提交观点

问题信息

排序
上传者：娃哈哈呀~
难度：
9条回答 15462浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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