我要招人

去企业版

首页 > 试题广场 >

下列排序算法的常规实现中，哪些空间复杂度是O(1)

[不定项选择题]

```
冒泡
```
```
选择
```
```
归并
```
```
快排
```
```
堆排序
```

牛客874504号

答案：ABE.

A.O（1）；

B.O（1）；

C.O（N）；

D.O(logN)~O（N）；

E.O（1）；

发表于 2015-03-31 22:43:35 回复(0)

更多回答

推荐

SunburstRun

A.B.E

冒泡排序,选择排序,堆排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引).

快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.

编辑于 2015-06-17 21:04:46 回复(1)

jdk

A,B,D,E

发表于 2015-01-12 16:31:17 回复(0)

程序猿Go师傅

编辑于 2019-10-21 20:56:16 回复(0)

牛客-007

答案：ABDE

除了归并排序需要一个同样大小的额外空间，其他都是常数级的空间复杂度

发表于 2015-01-14 14:21:47 回复(6)

yzzheng

快排是递归的，要借助一个工作栈来保存递归调用。最好情况o（log（n+1）），最坏情况o（n），平均情况o（logn）。

发表于 2018-11-15 17:29:53 回复(0)

bleedgreen

A,B,E

发表于 2015-06-03 12:29:15 回复(0)

大逗比

ABE是O(1)，快速排序递归调用占用空间，归并排序占用O(n).

发表于 2015-05-24 23:27:43 回复(0)

Aesthetic92

答案：选ABE

A：O(1)

B: O(1)

C: O(n)

D: O(log₂n)~O(n)

E: O(1)

发表于 2015-01-13 00:27:30 回复(0)

小雨落梧桐

ABE 除了归并(O(n)) 快速 (O(lgn)) 基排序 (O(rd + n)) 其他都是 0(1)

发表于 2015-04-17 11:02:14 回复(1)

人要学会珍惜

记:饿(需要额外空间）鬼(归并）炸鸡(基数）块(快排)，不在里面的就不需要额外空间。

发表于 2023-08-18 16:46:53 回复(0)

纠结的哈士奇在笔试

冒泡排序、选择排序、堆排序都是原地排序算法，不需要额外的空间，而快速排序虽然是原地排序算法但需要确定pivot，需要消耗栈空间，空间复杂度为O（logN），归并排序需要创建新的数组，空间复杂度为O（N）

发表于 2023-06-24 13:34:00 回复(0)

认证牛

插入排序，希尔排序，直接排序，堆排序，冒泡排序

发表于 2022-05-31 11:11:00 回复(0)

只求问心无愧

冒选插希堆皆为1

发表于 2020-08-27 15:43:43 回复(0)

燃烧黎明

皮皮虾哦，堆排序如果建堆时采用递归遍历的话也需要logn啊，如果不采用就是1，我反正是服了，要不看评论那得误导多少人?所以我每次都要看评论。。。

发表于 2020-04-29 23:56:33 回复(0)

阳光下的米雪

快排要是原地排序复杂度就为O(1)，要是递归调用，就是O(n)

发表于 2019-04-27 19:10:18 回复(0)

TTT爱吃糖

注意快排的空间复杂度，由于递归，所以是log（N)

发表于 2018-10-11 16:51:39 回复(0)

白露的包子

发表于 2018-07-17 19:01:40 回复(0)

左庶长

快排O（log2n）

归并O（n）

其他O（1）

发表于 2018-02-01 09:42:10 回复(0)

梦境迷离

堆排序如果不把删除的放在最后那么消耗O(N)空间，总以为算法只有一种实现方式吗

发表于 2017-12-12 21:32:53 回复(0)

wanlanwalan

冒泡排序,选择排序,堆排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引).

快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.

发表于 2017-05-06 10:46:22 回复(0)

烟消bug云散

快排有栈的消耗。没考虑这个

发表于 2016-07-21 09:37:24 回复(0)

提交观点

问题信息

C++工程师搜狗复杂度 2015 排序

来自：搜狗2015 C++工...

上传者：小牧魔法袋

难度：

29条回答 599收藏 26682浏览

下列排序算法的常规实现中，哪些空间复杂度是O(1)

问题信息

热门推荐

相关试题