数据结构
在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（）A、O（1）B、O（log2n）C、O（n2）D、O（nlog2n）
题目
在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（）
- A、O（1）
- B、O（log2n）
- C、O（n2）
- D、O（nlog2n）
相似问题和答案
第1题：
对n个元素的数组进行()，其平均时间复杂度和最坏情况下都为O(nlogn)。
A.希尔排序
B.快速排序
C.堆排序
D.选择排序
第2题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(55)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：快速排序在最坏情况下的时间复杂度退化到一般的交换排序，即为O(n2)。
第3题：
以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。
A．快速排序算法是不稳定的排序算法
B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)
C．快速排序算法是一种分治算法
D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
解析：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：cmax=n(n-1)／2=O(2)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
第4题：
● 若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为 （65） 。
第5题：
假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度(用 O记号)。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n)，得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时，即长度为n的数组划分后一个子数组为n-1，一个为0，算法为最坏情况，此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n)，得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂，假设数组每次划分为9/10：1/10，此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)，得到时间复杂度为O(nlogn)，因此在平均情况下快速排序仍然有较好的性能，时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为n-1和0的两个子数组，属于最坏情况。
第6题：
在对n个元素进行快速排序的过程中，最坏情况下需要进行______趟。
A．n
B． n-1
C． n/2
D． log2(下标)n
解析： 参见快速排序的过程。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称为快速排序法。快速排序法的关键是对线性表进行分割，以及对各分割出的子表再进行分割。
第7题：
对n个元素的数组进行(63)，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。
A．希尔排序
B．快速排序
C．堆排序
D．选择排序
解析：本题考查排序算法。
希尔排序的时间复杂度约为O(n1.4)。
快速排序在最坏情况下的时间复杂度为O(n2)。
选择排序的时间复杂度为O(n2)。
无论在什么情况下，堆排序的时间复杂度都是O(nlogn)。
第8题：
关于排序算法的以下说法，错误的是()
A.归并排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)
B.堆排序平均时间复杂度O(nlogn)，最坏时间复杂度O(nlogn)
C.冒泡排序平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)
D.快速排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)
第9题：
n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为______。
A．O(1)
B．O(1og2n)
C．O(n2)
D．O(n)
解析：最好情况下至少需要一趟排序，即比较n-1次。选项D为本题正确答案。
第10题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(65)。
A．O(log2n)
B．O(n)
C．O(nlog2/t)
D．O(n2)
解析：比较常用的排序算法的平均时间复杂度，以及最坏情况下的时间复杂度，可以知道快速排序最坏情况下的时间复杂度为O(n2)。