以30为基准，设一组初始记录关键字序列为 (30,15,40

[单选题]

以30为基准，设一组初始记录关键字序列为 (30,15,40,28,50,10,70)，则第一趟快速排序结果为（）

```
10，28，15，30，50，40，70
```
```
10，15，28，30,50，40，70
```
```
10，28，15，30，40，50，70
```
```
10，15，28，30，40，50，70
```

查看答案及解析

这个好玩吗？

选择B

快排的基本思想是：

1.先从数列中取出一个数作为基准数。

2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步，直到各区间只有一个数。

可以设置两个指针，一个从前往后遍历，一个从后往前遍历。先从后往前遍历，找到比基准小的和基准交换，然后从前往后遍历，找到比基准大的和基准交换......这道题一趟排序的具体交换过程如下：

初始序列：30 15 40 28 50 10 70，注意先从后往前找。

第一次交换30和10，因为10比30小，此时序列：10 15 40 28 50 30 70，然后再从前向后找

第二次交换40和30，因为40比30大，此时序列：10 15 30 28 50 40 70，然后再从后向前找

第三次交换30和28，因为28比30小，此时序列：10 15 28 30 50 40 70，一趟排序结束。

具体可以参考：http://blog.csdn.net/morewindows/article/details/6684558

发表于 2017-03-03 17:54:41 回复(3)

dragonaxz

答案是b？以30为基准，却把28排在30右面？所以说，我就知道是一道没答案的坑爹题

发表于 2016-12-18 16:25:11 回复(2)

菜小波

快排的实现是有很多方法的，单项扫描（从前向后，从后向前），双向扫描（前后指针同时，前后指针异步），三区分立法（针对可能有大量重复元素的数列，取三个指针分别指向待遍历元素区，主元素区左下标，主元素区右下标）等等，在分区的主元素的选择上又会有很多方法，往往我们图简单，可以直接取首元素，为了防止变成每次只能剔除一个元素成为O（n^2），往往使用首尾元素和mid元素三者取中值作为主元素来降低倒霉的可能性，但最保险的一定是O(nlogn)的是采用类似于希尔排序的部分算法思想，采用双指针寻求数列的中值元素（类似于那种简单的算法题：求数列中某个元素的位置，要求尽可能地快，而且不许把原数列排序）。

发表于 2020-04-11 22:52:28 回复(0)