首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 快速排序
题目

对关键码序列28,16,32,12,60,2,5,72快速排序（最常用的快速排序，以第一个关键码为基准）,使用挖坑法，从小到大一次划分结果为()

A.(2,5,12,16)28(60,32,72)

B.(2,16,5,12)28(60,32,72)

C.(2,16,12,5)28(60,32,72)

D.(5,16,2,12)28(60,32,72)

上一题 下一题
解答

正确答案是 B

一趟排序结果为5，16，2，12，28，60，32，72。

一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
C 8条回复 评论
匀斋

非常感谢，大学学习不刻苦，现在上班补一补

发表于 2024-04-04 22:00:00
0 0
我的艾迪不寻常

设计行业没有个五六年经验都不好意思说自己是设计师

发表于 2023-06-22 23:00:00
0 0
雪糕乐

快速排序有很多种，以最常用的一种为主吧。

发表于 2018-10-13 11:06:31
0 0
雪糕乐

快速排序有很多种，以最常用的一种为主吧。

发表于 2018-10-13 11:06:18
0 0
浅色回忆

做了几遍都是：5,16,2,12,28,60,32,72

发表于 2018-10-13 11:06:03
0 0
浅色回忆

难到不是(5，16，2，12) 28 (60，32，72)吗。。。

发表于 2018-10-13 11:05:52
0 0
冬季恋歌

以28为基准，因为一般都是以a[0]基准，从两端开始扫描

规则是：
1.从右边扫描时，记录比基准小的元素的下标j
2.从左边扫描时，记录比基准大的元素的下标i
3.  if（若此时两个下标 i = j）{
        当前下标的元素与基准进行交换，结束一次划分
        把原有序列分为两端重新划分
    }
    else{
        执行第四步骤
    }
4.这时开始交换两个下标对应的元素
5.以当前的位置开始，继续从1开始
第一次交换32和5    28 16 5 12 60 2 32 72
第二次交换60和2    28 16 5 12 2 60 32 72
第三次交换28和2    2 16 5 12 28 60 32 72

第一次划分完成    这题没有正确选项 因为再第一次划分中，12是不会和其他元素交换的

发表于 2018-10-13 11:05:29
0 0
冬季恋歌

原始为：

28 16 32 12 60 2 5 72
i是左到右找小于28数，j是右到左找小于28数，j先动。
j找到5，i动找到32。两者互换。有：
28 16 5 12 60 2 32 72
j找到2，i找到60互换有：
28 16 5 12 2 60 32 72
j i相遇，i和28换位子：

2 16 5 12 28 60 32 72

发表于 2018-10-13 11:05:11
0 0
问题信息
分类：数据结构 - 快速排序
难度:
最新校招难题刷题，快来进刷题群吧
相关试题