考点
数据结构-排序-快速排序
面5笔5对下列关键字序列用快速排序法进行排序时,速度最快的情形是()
A.{21,25,5,17,9,23,30}
B.{25,23,30,17,21,5,9}
C.{21,9,17,30,25,23,5}
D.{5,9,17,21,23,25,30}
前往“校招VIP”小程序，刷题更快
最新校招难题刷题，快来进刷题群吧
解答
正确答案是 A
pivotkey的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。
21正好是序列的正中，所以排除B，D。
A经过一次排序后结果为9，17，5，（21），25，23，30
C经过一次排序后结果为5，9，17，（21），25，23，30
对于子序列9，17，5和5，9，17，后者在有序状态下用快速排序方法的速度没有前者快，答案为A。
万成
2018-10-13 15:49:30
0
0
寒山远火
2018-10-13 15:49:22
0
0
虹猫
2018-10-13 15:48:50
0
0
途安米
2018-10-13 15:48:33
0
0
落地成盒
2018-10-13 15:48:20
概念： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数据变成有序 序列 。
特点： 最坏情况 时间复杂度 为o（n 2 ）。因为 最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。最好情况： 如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了， 排序的大体如下图所示，假设有1到8代表要排序的数，快速排序会递归log（8）=3次，每次对n个数进行一次处理，所以他的时间复杂度为n*log(n)。
题目：越有序，时间复杂度越高。数据结构中，有一个逆序数的概念。如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个 逆序 。 如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。
题目中：A8 B17 C11
0
0