设一组初始记录关键字序列为(65,56,72,99,86,2

[单选题]

设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）

```
34，56，25，65，86，99，72，66
```
```
25，34，56，65，99，86，72，66
```
```
34，56，25，65，66，99，86，72
```
```
34，56，25，65，99，86，72，66
```

查看正确选项

Deep-learning算法工程师

这题有问题。。。不一定这样排

发表于 2019-03-13 18:52:11 回复(0)

宫保鸡丁没萝卜

根据快速排序算法，选择第一个关键字65作为基准，最终把65放在它应该在的位置，65左边的数小于65，右边的大于65。我们把这八个数字的位置标记为从1到8.high指向最后的66，low指向第一个65。从后向前比较，遇到比65小的数就放在low处，然后low向前移动，遇到比65大的数，把这个数放在high处，然后high继续向左移动，以此类推。排序过程开始：先保存下来基准数65，然后从后向前比较，66>65，不动，high向前移动指向34，34<65，然后把34放在low，low向右移动指向56，56<65,不动，low继续右移指向72，72>65,把72放在high指向的位置，即第7个数的位置，然后high向前移动指向25.25<65，所以把25放在low指向的位置，即第三个位置，然后low向前移动一位，指向第四个数99.99>65，所以把99放在high的位置，即第6个数的位置。high左移一位指向第五个数86，86>65不动，high继续左移，此时high和low重合都指向了第四个数，跳出循环。第四个数的位置就是基准65的位置，把65放在第四个数的位置，即完成了第一趟快速排序。

序列变化过程：

65 56 72 99 86 25 34 66

34 56 72 99 86 25 66

34 56 99 86 25 72 66

34 56 25 99 86 72 66

34 56 25 86 99 72 66

34 56 25 65 86 99 72 66

即选项A为正确答案。

编辑于 2017-01-24 19:34:16 回复(2)

fghfghggh

为啥有两种快排思想

从前往后比65小的放到left数组，比65大的放在right数组，然后递归，这样的快排思想不对吗？被牛客上的快排搞晕了，到底哪个是对的

发表于 2018-10-07 14:26:55 回复(4)

zt_xcyk

默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
循环 2-3 步骤，直到 low=high，该位置就是基准位置。
把基准数据赋给当前位置。

我是这样排的和答案一致。

发表于 2020-07-29 10:23:34 回复(0)