首页 > 试题广场 >

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

[不定项选择题]
下列排序算法的常规实现中,哪些空间复杂度是O(1)
  • 冒泡
  • 选择
  • 归并
  • 快排
  • 堆排序
推荐
A.B.E
冒泡排序,选择排序,堆排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引).
快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
编辑于 2015-06-17 21:04:46 回复(1)
jdk头像 jdk
A,B,D,E
发表于 2015-01-12 16:31:17 回复(0)
编辑于 2019-10-21 20:56:16 回复(0)
答案:ABDE
除了归并排序需要一个同样大小的额外空间,其他都是常数级的空间复杂度
发表于 2015-01-14 14:21:47 回复(6)
快排是递归的,要借助一个工作栈来保存递归调用。最好情况o(log(n+1)),最坏情况o(n),平均情况o(logn)。
发表于 2018-11-15 17:29:53 回复(0)
A,B,E
发表于 2015-06-03 12:29:15 回复(0)
ABE是O(1),快速排序递归调用占用空间,归并排序占用O(n).
发表于 2015-05-24 23:27:43 回复(0)
答案:选ABE
A:O(1)
B: O(1)
C: O(n)
D: O(log2n)~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)
注意快排的空间复杂度,由于递归,所以是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)
冒泡排序,选择排序,堆排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引).
快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
发表于 2017-05-06 10:46:22 回复(0)
快排有栈的消耗。没考虑这个
发表于 2016-07-21 09:37:24 回复(0)