快速排序在最坏情况下的时间复杂度与下面（）算法最坏情况下的

[不定项选择题]

快速排序在最坏情况下的时间复杂度与下面（）算法最坏情况下的时间复杂度相同。

```
堆排序
```
```
Shell 排序
```
```
冒泡排序
```
```
基数排序
```

查看答案及解析

Jino.

选C。

常用排序算法复杂度情况如下图：

由上图可知

在最坏情况下，快速排序的时间复杂度与冒泡排序相同，均为O(n²）。

Shell排序在最坏情况下时间复杂度为O（nlog²n）。

基数排序在最坏情况下时间复杂度为O（n*k）。

堆排序在最坏情况下时间复杂度为O（nlogn）。

综上，选C。

编辑于 2021-10-01 18:39:50 回复(2)

天尊墨宇

选择BC项，理由如下

希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。希尔排序的运行时间依赖于增量序列的选择，最坏情形运行时间为O(n²)

发表于 2020-06-16 20:40:52 回复(0)

牛客218196695号

快速排序在最坏的情况下即为最初始得情况已排好序，此时得一趟快排与冒泡排序类似，所以最坏情况与，O(n^2)

发表于 2020-05-22 17:34:59 回复(0)

sincebreeze

首先堆排序的时间复杂度只为O(nlogn)，在最好最坏平均情况下都是，冒泡排序当序列与排序序列正好相反时时间复杂度最坏为O(n2)，基数排序一直O(d(n+r)),而shell排序在最坏情况下也为O(n2)

发表于 2019-12-30 15:14:27 回复(0)

白驹之过隙

选BC。

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

最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。时间复杂度为O（n²）

选项A堆排序：依照完全二叉树的特性，最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子。初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)
选项B希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。希尔排序的运行时间依赖于增量序列的选择，最坏情形运行时间为O(n²)
选项C冒泡排序：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。最坏的情形运行时间为O(n²)。
选项D基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。时间复杂度最坏情况O(d(r+n))