我要招人

去企业版

首页 > 试题广场 >

假设一个数组采用快速排序，则下面的选项中，不可能是第3趟排序

[不定项选择题]

假设一个数组采用快速排序，则下面的选项中，不可能是第3趟排序结果的是

```
4, 8, 6, 10, 12, 16, 14
```
```
10, 4, 6, 8, 12, 14, 16
```
```
8, 4, 6, 12, 10, 14, 16
```
```
4, 8, 6, 12, 10, 16, 14
```

查看答案及解析

Yanshsf

a应该也是错的

因为按照快排，最后结束条件是left==right,所以每一趟排序一定会有一个正确的数字占正确的坑位，3趟应该至少有3个数字在正确位置

本题排序后结果为4,6,8,10,12,14,16

A选项， 4, 8, 6, 10, 12, 16, 14 有3个数字在正确位置，错误

B选项， 10, 4, 6, 8, 12, 14, 16 有3个数字在正确位置，错误

C选项， 8, 4, 6, 12, 10, 14, 16 有2个数字在正确位置，正确

D选项， 4, 8, 6, 12, 10, 16, 14 有1个数字在正确位置，正确

发表于 2021-06-26 17:53:28 回复(8)

键盘盘盘盘

正确答案ACD我选了B😀

发表于 2021-10-15 21:17:09 回复(5)

Lysen-Goto

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为 “一趟”。在快速排序中，满足左边都小于 x，右边都大于 x 的位置，称为 “基点”。对于 “基点” 的个数，有如下规律：

第一趟排序，确定一个基点
第二趟以及以后的排序，确定一个或两个基点
当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个基点
当第一趟元素确认位置不是最左或最右时，第二趟能确认 2 个基点

我们将 “基点” 标出来：

选项 A，[ 4, 8, 6, 10, 12, 16, 14 ]，如果第一趟是 4，第二趟可以是 10 或者 12，由于 10 和 12 都在中间，第三趟必须有两个基点，但是没有，不符合题意

选项 B，[ 10, 4, 6, 8, 12, 14, 16 ]，如果第一趟是 16，第二趟可以是 14，第三趟可以是 12，它们都在最右边，每趟只需要确认一个基点，符合题意

选项 C，[ 8, 4, 6, 12, 10, 14, 16 ]，每趟至少确认一个基点，这里只有两个，不符合题意

选项 D，[ 4, 8, 6, 12, 10, 16, 14 ]，每趟至少确认一个基点，这里只有一个，不符合题意

综上所述，答案选择 A C D

发表于 2023-08-22 16:04:08 回复(1)

牛客494072386号

快速排序一次排完，pivot左边的元素不应该都比pivot小，右边的元素都比pivot大吗？b为什么对啊？

发表于 2021-08-10 14:53:38 回复(1)

Hayle

这题目，我感觉A是对的呢？？？

发表于 2021-07-16 21:09:13 回复(0)

Master·Bruce

若初始数组是12、6、8、10、12、14、16，每次以最左边的元素为pivot，后两次都是对左半边的子列进行排序，得到的结果不就是A吗？

发表于 2021-07-16 21:46:32 回复(0)

和鲨鱼一起冲浪

A选项

快速排序的第三趟会以一个基准元素为分界点，将数组分成两个子数组，并将小于基准元素的值移动到左边，大于基准元素的值移动到右边。因此，为了确定这个数组是否是快速排序的第三趟结果，我们需要找到在第三趟中使用的基准元素。

通常，快速排序的实现方法是选择第一个元素作为基准元素。因此，我们可以将这个数组的第一个元素4作为基准元素进行分区操作，得到以下两个子数组：

左子数组：4, 6

右子数组：8, 10, 12, 16, 14

在第三趟中，左子数组和右子数组都不会再进行分区操作，因为它们的长度都小于等于1。因此，如果这个数组是快速排序的第三趟结果，那么它的左半部分必须已经完成了分区操作，将小于等于4的元素移到了左边，大于4的元素移到了右边。但是，在这个数组中，6比4大，因此左半部分没有完成分区操作。因此，这个数组不可能是快速排序的第三趟结果。

发表于 2023-03-18 14:32:31 回复(2)

terry_gjt

我是这么想的，如果是最理想的情况，就是枢轴每次都恰好选到中间，这样的话3次足够使整个序列有序

那么考虑最坏的情况，B 三次分别选16、14、12

A的话第一次选10，第二次左右都需要选一个，只能4和12，第三次没了，所以不可能

发表于 2022-10-11 15:03:26 回复(0)

vincent_h

B 是正确的,

第一次选 16 为 pivot, 左边都小于 16, 满足

第二次选 14 , 左边都小于 14 , 满足

第三次选 12 , 左边都小于 12, 满足

发表于 2022-03-22 16:49:25 回复(0)

你的微笑Haru

快排每次至少有一个数字会落到最终位置，因此第三次排序后至少又三个数字位置正确，因此A是对的

发表于 2022-01-04 19:36:50 回复(0)

提交观点

问题信息

C++工程师前端工程师 PHP工程师百度 2020 Java工程师

上传者：小小

难度：

10条回答 244收藏 4251浏览

假设一个数组采用快速排序，则下面的选项中，不可能是第3趟排序

问题信息

热门推荐

相关试题