首页 > 试题广场 >

设一组初始关键字记录关键字为（19,15,12,18,21,

[单选题]

设一组初始关键字记录关键字为（19,15,12,18,21,36,45,10),则以19位基准记录的一趟快速排序结束后的结果为()

```
10,15,12,18,19,36,45,21
```
```
10,15,12,18,19,45,36,21
```
```
15,10,12,18,19,36,45,21
```
```
10,15,12,19,18,45,36,21
```

推荐

passi0n

一个不断挖坑填坑的过程。

按题意，先把a[0]挖坑，然后从tail开始找第一个小于pivot的值，这里是a[7]=10，把10填到之前的那个坑中，同时a[7]变成来一个坑。再从前往后，找到第一个大于pivot的值a[4]=21,用21填之前的那个坑，并在a[4]挖来个坑。再从a[6]开始向前寻找第一个小于pivot的值。。。然后与前面的相遇了，把pivot填进那个坑就得到最终结果。

pivot＝19； [], 15,12,18,21,36,45,10

10 ,15,12,18,21,36,45,[]

10,15,12,18,[],36,45,21

最后填坑： 10,15,12,18,19,36,45,21

编辑于 2015-12-29 09:46:41 回复(3)

fenf

这题最强的是交换和填坑的结果是一样的

发表于 2018-09-10 15:22:29 回复(0)

渣渣~~

以19为基准，那么从15开始从左向右找比19大的，找到21，然后从又向左找比19小的，找到10，21与10交换位置，然后因为19要在比它小的10的前面，交换10和19点位置

发表于 2017-03-20 14:38:57 回复(0)

尐短腿

从后往前找小的填缺口，从前往后找大的循环填缺口知道找到的数和缺口相遇则把pivot 填入缺口这是一趟排序、、都找第一个大的或者第一个小的！！！！

发表于 2016-06-13 10:08:52 回复(0)

牛客516922号

可以先从左开始扫描，也可以先从右开始扫描。但这里先从左扫描没有可选答案，从右扫描恰有一答案

发表于 2016-03-01 23:37:21 回复(0)

全三三

先从后往前扫描，比19小的与19交换，再从前往后扫描，比是19大的与19交换

依次为：

19 ， 15 ，12 ，18 ，21， 36 ， 45 ，10 // 从后往前扫描 10比19小，交换
10 ， 15， 12,，18，21，36，45，19，从前往后扫描，21 比19大，交换
10 ， 15 ， 12 ，18 ， 19 ，36， 45， 21 // 19前边都比19小，后边都比19大，一趟比较结束

发表于 2015-09-11 12:18:29 回复(2)

jranzjm

牛客的快排序列都是用的挖坑法，用交换法的同志们注意了。。。

发表于 2017-12-13 13:14:46 回复(1)

答案略

以19为基准进行一趟排序，排序后左边的元素比19都小，右边的元素都比19大，故排除D
排序先从右到左找一个比19小的数(10)，然后与19所在的位置进行交换，故可以排除C
再从左到右找一个比19大的数(21),然后与19交换，此时19在末尾，交换后可以排除B
再从右到左找比19小的数，未找到，此时，首尾指针相遇，结束此趟排序，得到答案A的结果

发表于 2017-06-27 11:42:54 回复(0)

邢涌芝

本题交换和填坑是结果是一样的，都是A。
交换法过程如下，参考快排图解。
设置19为基准数。先 j 从右往左找比19小的，后 i 从左往右找比19大的，交换之，反复，直到左右 i j 相会，交换基准数和相会位置的数。

19,15,12,18,21,36,45,10 ，由于 10<19,21>19，交换21和10.
19,15,12,18,10,36,45,21 ，交换完成。
19,15,12,18,10,36,45,21，继续，j从后往前找，由10<19，故在10处与i相会。交换19和10
10,15,12,18,19,36,45,21，第一趟排序完毕。

发表于 2019-03-03 19:26:00 回复(0)

RockMan

快速排序：

实现原理： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

要点：快排实现方式多种多样，一定要熟悉最为标准的方式，这样才可以正确回答类似选择题和填空题。

发表于 2015-09-11 15:47:51 回复(0)

阳光下的时光

1）先从最后一个开始向前比较，找到比19小的数10，和19交换位置；

结果为：10, 15, 12, 18, 21, 36, 45, 19

2）再从第一个开始向后比较，找到比19大的数21，和19交换位置；

结果为：10, 15, 12, 18, 19, 36, 45, 21

3）然后从21开始向前比较，找到比19小的数，未找到，然后遇到19，排序结束；

结果为：10, 15, 12, 18, 19, 36, 45, 21（和步骤2一样）

发表于 2017-09-07 16:25:02 回复(0)

没名字的嘀嘀嘀

*****我学的快排可是有三次分区的方式，我哪知道你说哪一种呀

编辑于 2023-09-18 17:49:23 回复(0)

我没得啃老

为什么和我敲的时候感觉不太一样啊？‘

——————是我天真了，不好意思，一样的

以19为基准：

第一趟：19 15 12 18 10 36 45 21

第二趟：10 15 12 18 19 36 45 21

```cpp

void sortArrayNums(vector<int>& nums,int lo,int hi){

// 快排模板

if(lo >= hi){

return;

}

// 对nums[lo..hi]进行切分

// 使得nums[lo..p-1] <= nums[p] <= nums[p+1...hi]

// 这里默认每次传入的p都是第一个数了呗

int p = partition(nums,lo,hi);

sortArrayNums(nums,lo,p-1);

sortArrayNums(nums,p+1,hi);

}

// 函数作用：保证p右边的都比p大，左边的都比p小

int partition(vector<int>& nums,int lo,int hi){

// 这里默认每次传入的p都是第一个数了呗

int pivot = nums[lo];

// 区间边界控制：i,j定义为开区间

// [lo,i) <= pivot; (j,hi] > pivot

int i = lo+1, j = hi;

// 当i>j时循环结束，以保证区间[lo,hi]都被覆盖

while(i <= hi){

while(i < hi && nums[i] <= pivot){

i++;

// 此while结束时恰好nums[i] > pivot（比基准值大）

}

while(j > lo && nums[j] >pivot){

j--;

// 此while结束时恰好nums[j] <= pivot（比基准值小）

}

if(i >= j){

break;

}

// 互换nums[i] 和 nums[j]

swapArray(nums,i,j);

}

// 将基准值与nums[j]互换，达到基准值左边元素都小，右边元素都大的效果

swapArray(nums,lo,j);

return j;

}

```

发表于 2022-10-11 17:37:05 回复(0)

aaa---

<p>快排交换法和填坑法</p>

发表于 2020-11-24 22:30:14 回复(0)

昵称就是这了

前后哨兵，从后先开始，依次交替进行换序，直到，一分为二，左边小于区，右边大于区即可

发表于 2019-12-03 22:08:38 回复(0)

Z3R0

我眼睛不好，看错了

发表于 2019-10-27 11:39:02 回复(0)

Mr_zhl

先从后往前

10，15,12,18,21,36,45,19

在从前往后

10,15,12，18,19,21,36,45,21

发表于 2019-04-16 19:36:08 回复(0)

牛客7458771号

一个不断挖坑填坑的过程。按题意，先把a[0]挖坑，然后从tail开始找第一个小于pivot的值，这里是a[7]=10，把10填到之前的那个坑中，同时a[7]变成来一个坑。再从前往后，找到第一个大于pivot的值a[4]=21,用21填之前的那个坑，并在a[4]挖来个坑。再从a[6]开始向前寻找第一个小于pivot的值。。。然后与前面的相遇了，把pivot填进那个坑就得到最终结果。 pivot＝19； [], 15,12,18,21,36,45,10 10 ,15,12,18,21,36,45,[] 10,15,12,18,[],36,45,21 最后填坑： 10,15,12,18,19,36,45,21

发表于 2016-09-12 23:58:57 回复(0)

HonestFox

我靠！居然眼花了

发表于 2016-09-03 16:49:42 回复(0)

我的小肚腩。

用快速排序，不停按照轴心转。

发表于 2015-09-11 10:19:55 回复(0)

哈喇子流了

发表于 2015-09-11 08:49:40 回复(0)

提交观点

问题信息

排序

来自：2017CVTE校招在...

难度：

21条回答 710收藏 14487浏览

设一组初始关键字记录关键字为（19,15,12,18,21,

问题信息

热门推荐

相关试题