我要招人

去企业版

首页 > 试题广场 >

设一组初始关键字记录关键字为（ 12,15,1,18,2,3

[单选题]

设一组初始关键字记录关键字为（ 12,15,1,18,2,35,30,11 ），则以 12 为基准记录的一趟快速排序结束后的结果为（）

```
11，1，2，12，35，18，30，15
```
```
1，2，11，12，15，18，35，30
```
```
以上都不是
```
```
11，2，1，12，18，35，30，15
```

查看答案及解析

牛客2505702号

快速排序里的挖坑填补法：以12为标准值，从右开始找比12小的值，首先是11，把11放在12的那个位置，把12放在11的位置，在从左找比12大的值15，把15放在12的新位置（原11的位置）之后变成 11，12，1，18，2，35，30，15.

在新的一轮开始，从右开始找12 小的数是2，把2放在12的位置，12放在2的位置，在从左找比12大的数18，把18放在12的新位置上（原2的位置）变成11，2，1，12，18，35，30，15.

发表于 2017-08-03 09:16:45 回复(11)

korky

测试的不是答案D 没有答案的 11怎么跑到最前面去了

发表于 2017-05-08 16:54:59 回复(8)

听雨眠醉蝉声

快排如下

12 15 1 18 2 35 30 11

11 15 1 18 2 35 30 12

11 12 1 18 2 35 30 15

11 2 1 18 12 35 30 15

11 2 1 12 18 35 30 15

发表于 2017-09-24 09:03:57 回复(1)

LiuJiayu

发表于 2017-03-02 10:37:59 回复(5)

麦垛上的守望者

快排有两种交换方式，第一种轴心数按兵不动，等其他数字交换完了最后和轴心数交换。第二种，每次发现符合要求的数时就和轴心数做一次交换，右左右左，直到最后一次交换。相较于第一种，第二种显然多了将近一倍的数据交换，所以通常情况下快排指的是第一种快排。

发表于 2018-05-25 21:44:55 回复(5)

修羅君

按照标准的快速排序公式来的话，答案却是是D

建议算错的可以去找一下标准的快排，否则以后这道题还是没标准

发表于 2017-03-29 21:43:36 回复(0)

小游侠UnoW

arr[] = 12,15,1,18,2,35,30,11

准基为 p = 12，l=0，r=其长度；

------------------------------------------------------------------------------------------------------------

步骤 1:

{

从右往左扫描r-- 且 r > l，若出现比 p 小的数，arr[l] = arr[r];

从左往t右扫描l++ 且 l < r，若出现比 p 大的数，arr[r] = arr[l];

}

若 l < r 成立，重复步骤 1；不成立，arr[l] = p;

这样就实现了比准基 p=12 小的数全部在左边，比准基大的数据全部在右边；

------------------------------------------------------------------------------------------------------------

以上操作也正是快速排序的一躺操作流程；

=================================

*实践一下：

p = 12;

arr[] = 12,15,1,18,2,35,30,11

1: right to left， 11( 所以 arr[left] = 11 )，15，1，18，2，35，30，11（因为 11<p ）

2: left to right，11，15（因为 15>p），1，18，2，35，30，15( 所以 arr[right] = 15 )

3: left < right == true

4: right to left，11，2( 所以 arr[left] = 2 )，1，18，2（因为 2<p ），35，30，15

5: left to right，11，2，1，18（因为 18>p ），18( 所以 arr[right] = 18 )，35，30，15

6: left < right == true

7: right to left, right减1后，right > left 不成立，推出

8: left < right == false，所以 arr[left] = p

9: 最终结果：11，2，1，12，18，35，30，15

编辑于 2019-12-31 12:25:58 回复(0)

H14ugust

实现了一下"挖坑填补"的快排第一趟打印的确实是D

    private void quicksort2(int left,int right){
        int i,j,t,temp;
        if(left > right)return;
        temp = a[left];
        i = left;
        j = right;
        int temp_position=left;
        //移动哨兵
        while (i<j){
            if (a[j]<=temp)
            {   t=a[temp_position];
                a[temp_position]=a[j];
                a[j]=t;
                temp_position=j;
            }
            if (a[i]>temp)
            {
                t = a[i];
                a[i] = a[temp_position];
                a[temp_position] = t;
                temp_position=i;
            }
            i++;
            j--;
            for (int e:a) {
                System.out.print(e);
                System.out.print(" ");
            }
            System.out.print("\n");
        }
        //二分递归，左，右
        //quicksort2(left,temp_position-1);
        //quicksort2(temp_position+1,right);
    }

编辑于 2019-04-09 22:55:58 回复(0)