试题-对下列关键字序列用快速排序法进行排序时,速度最快的情形是()

题目

对下列关键字序列用快速排序法进行排序时,速度最快的情形是()

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}

上一题 下一题

解答

正确答案是 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。

C 9条回复评论

采苓子

老师讲得真好，通俗易懂

发表于 2022-12-04 22:00:00

0 0

琼华

不过还有待完善,挺好的，不错的资源。

发表于 2021-09-10 14:25:00

0 0

万成

平均逆序数是基于比较的算法下界，而逆序数越小，插入排序越快因为每次只能消除一个逆序数，反过来不能得到则逆序数越大，对插入排序来说越慢。对快速排序不能用吗

发表于 2018-10-13 15:49:30

0 0

寒山远火

若序列原本有序此时快排相当于没分块，每次排序只把枢轴去除掉，也就是一颗斜树，深度为n这是最差墨情况，最好时是枢轴取得合理使树的深度为logn。

发表于 2018-10-13 15:49:22

0 0

雨声敲敲

快排和序列的初始顺序有关，选择的基准数把整个序列划分得越均匀，排序速度越快。

发表于 2018-10-13 15:49:12

0 0

资深90后

pivotkey的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。一般第一个数作为基准。

发表于 2018-10-13 15:49:00

0 0

虹猫

想问一下这里的快排的方法默认是什么啊？我采用的是算法4那本书快排方法，对A和C进行一次排序后，A是 17,9,5,21,25,23,30，C 是 5,9,17,21,25,23,30，这样一来我就不知道选什么了？？？求解

发表于 2018-10-13 15:48:50

0 0

途安米

首先应掌握的知识点是快排队有序数列的速度最慢把d排除

然后看abc不好看出来结果，但是把这三个选项进行一次排序之后就能发现bc基本有序，所以是啊

发表于 2018-10-13 15:48:33

0 0

落地成盒

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

特点： 最坏情况时间复杂度为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

发表于 2018-10-13 15:48:20

0 0

问题信息

分类：数据结构 - 快速排序

难度:

最新校招难题刷题，快来进刷题群吧