我要招人

去企业版

首页 > 试题广场 >

算法的时间复杂度为O(nlogn)、空间复杂度为O( 1)的

[单选题]

算法的时间复杂度为O(nlogn)、空间复杂度为O( 1)的排序算法是( )。

```
快速排序
```
```
归并排序
```
```
堆排序
```
```
选择排序
```

推荐

白驹之过隙

选C 。考察的是不同排序算法的时间复杂度和空间复杂度。

选项A：快速排序，从数列选定一个基准值进行分区，大于基准值的放在右区，小于基准值的放在左区，依次继续对左右两区继续进行基准分区，直到分区中只有一个数为止。时间复杂度为O(nlog₂n),空间复杂度为O(nlog₂n)
选项B：归并排序，分而治之然后合并，即先使每个子序列有序，再使子序列段间有序，最后合并各个有序的子序列为有序的完整序列。时间复杂度为O(nlog₂n)，空间复杂度为n。
选项C：堆排序，利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征。时间复杂度O(nlog₂n),空间复杂度为O(1)
选项D：选择排序，每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。时间复杂度为O(n²),空间复杂度为O(1)

编辑于 2019-09-02 14:22:05 回复(1)

Tauruschill

快速排序使用递归调用，因此需要至少O(logn)的栈空间。归并排序每次合并借助临时数组，需要空间O(N)。

发表于 2019-11-15 10:09:00 回复(0)

一天一到lc

快速排序，归并排序，堆排序的时间复杂度均为O（nlogn），空间复杂度依次递减

发表于 2019-08-30 14:34:47 回复(0)

小左乀

快排：时间（nlogn）空间（nlogn）不稳定

归并：时间（nlogn）空间（n）稳定

堆：时间（nlogn）空间（1）不稳定

选择排序：时间（n^2）空间（1）不稳定

发表于 2019-08-30 14:27:55 回复(0)

夏荷浅梦

这道题目选C。

考察的是对不同排序方法时空复杂度的认识。

A选项，快速排序的时间复杂度为O(nlogn)，空间复杂度也是O(nlogn)。

B选项，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

C选项，堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

D选项，选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

因此只有C选项符合题目要求，故选C。

编辑于 2019-08-31 06:20:40 回复(0)

J-Young

很经典的题目，我认为不要单靠记忆来处理这些题目，还是要真正理解。

A：快速排序，虽然在算法当中只使用到了两个指针，分别从数组的两端相互靠近。但是，算法是采用递归的样式来进行设计的，所以平均情况下递归的深度为logn的话，最终占用的空间为2*logn。空间复杂度为O(logn)也没毛病。（评论里面写O(nlogn)的同学，你们是怎么想的呢？）

B:归并排序，归并排序算法也用到了递归算法的思想。每一次递归都会产生一些诸如指示数组范围的指针变量，一直递归至仅有1个元素的数组区间为止，由于归并排序算法每次产生两个递归调用。计算空间复杂度类似于查一下满二叉树的结点个数，为2n-1。空间复杂度为O(n)没毛病。

C：堆排序，堆排序是通过结点本身所有的指针来建立起一棵树的，无非是指针的指来指去，也没有递归调用。复杂度为O(1)也没问题。

D：选择排序，没有使用递归调用，函数当中直接用了一个双层for循环，用temp，temp_index变量就完成了。所以空间复杂度为O(1)没毛病。

发表于 2021-07-11 16:29:05 回复(0)

牛客小妞号

考察的是对不同排序方法时空复杂度的认识。

A选项，快速排序的时间复杂度为O(nlogn)，空间复杂度也是O(nlogn)。

B选项，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

C选项，堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

D选项，选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

因此只有C选项符合题目要求，故选C。

发表于 2021-06-03 13:13:58 回复(0)

jingjinghao

基于树形结构排序的算法的复杂度都为nlogn，不懂空间复杂度是怎么看的？

发表于 2019-09-01 16:51:31 回复(0)

Aileen👐

发表于 2018-12-08 21:20:56 回复(0)

提交观点

问题信息

排序

上传者：zsw3

难度：

9条回答 120收藏 4118浏览

算法的时间复杂度为O(nlogn)、空间复杂度为O( 1)的

问题信息

热门推荐

相关试题