我要招人

去企业版

首页 > 试题广场 >

设一组初始关键字记录关键字为(20，15，14，18，21，

[单选题]

设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。

```
10，15，14，18，20，36，40，21
```
```
10，15，14，18，20，40，36，21
```
```
10，15，14，20，18，40，36，2l
```
```
15，10，14，18，20，36，40，21
```

查看答案及解析

Leon_z

快排中选择一个基准值，然后在左右两边分别进行比较排序，所有大于基准值的整数移到基准值右边，所有小于基准值的整数移到基准值左边。使用两个指针（low，high）从数组的两端向中间扫描。

原始数组为：20，15，14，18，21，36，40，10；low指向20，high指向10

1、low指向20，high指向10，基准为20：10比20小，交换：10，15，14，18，21，

36，40，20；

2、low指向10，high指向20，基准为20：10比20小，不交换，low++；

3、low指向15，high指向20，基准为20：15比20小，不交换，low++；

4、low指向14，high指向20，基准为20：14比20小，不交换，low++；

5、low指向18，high指向20，基准为20：18比20小，不交换，low++；

6、low指向21，high指向20，基准为20：21比20大，交换：10，15，14，18，20，

36，40，21；

7、low指向20，high指向21，基准为20：21比20大，不交换，high--；

8、low指向20，high指向40，基准为20：40比20大，不交换，high--；

9、low指向20，high指向36，基准为20：36比20大，不交换，high--；

10、high==low，退出循环，一趟快排结束。

所以第一趟结束：10，15，14，18，20，36，40，21

编辑于 2018-08-28 08:19:01 回复(4)

MrWang201901091834481

方法其实很简单：分别从初始序列“20，15，14，18，21，36，40，10；”两端开始“探测”。先从右往左找一个小于20的数，再从左往右找一个大于20的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边（i）和最右边（j）。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字20。让哨兵j指向序列的最右边（即j=8），指向数字10。

具体步骤：

1.哨兵j一步一步地向左挪动（即j--），直到找到一个小于20的数（10）停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于20的数（21）停下来，然后交换两者位置，即‘20，15，14，18，10，36，40，21’

2.重复1，即哨兵j向左找小于20的数（指向10），同时哨兵i指向10，此时哨兵i和哨兵j相遇（即满足了i=j,），将基准数20和当前相遇位置（i=j）指向的数10进行交换，即‘10，15，14，18，20，36，40，21’.至此第一趟快排结束。

参考链接：https://blog.csdn.net/adusts/article/details/80882649

发表于 2019-07-02 19:40:55 回复(0)

＆70

双路快排的答案是A，单路从后往前快排是10.15.14.18.20.21.36.40，不在选项中。可能还有其他快排方式，结果不在选项中。所以我觉得题目还是直接说明是哪种排序方式比较好。

发表于 2019-06-04 11:24:52 回复(0)

LClover

快速排序的思想：就是按照“基准”将记录分割成两个独立的部分，左边都小于“基准”，右边都大于“基准”。

然后采用挖坑法(详情可参考该网址，流程十分清晰：http://www.sohu.com/a/246785807_684445)：

编辑于 2019-10-10 18:55:53 回复(0)

小章鱼爱吃丸子

注意双路快排和单路快排

发表于 2019-06-15 18:34:58 回复(0)

一张钞票

快排的题感觉特别坑，快排又不是只有一种快排的方法。

发表于 2018-08-17 11:20:51 回复(0)

牛客1042593号

第一轮

10，15，14，18，20，21，36，40

发表于 2018-02-24 17:45:12 回复(1)

牛客1613089号

为什么21跑到最后去了

发表于 2018-01-17 14:19:57 回复(1)

初入java

  快排中选择一个基准值，然后在左右两边分别进行比较排序，所有大于基准值的整数移到基准值右边，所有小于基准值的整数移到基准值左边，第一遍排序就得到A的答案

发表于 2017-11-03 11:20:11 回复(0)

梓泽zize

不应该是先从后开始吗

发表于 2017-07-07 12:49:40 回复(1)

假洒脱

快排划分的数组可参考d，划分完先对左边进行递归排序。第一次递归的结果就是答案A

发表于 2017-06-22 12:02:28 回复(1)

提交观点

问题信息

数组

上传者：阿奻_

难度：

11条回答 248收藏 7750浏览

设一组初始关键字记录关键字为(20，15，14，18，21，

问题信息

热门推荐

相关试题