首页 > 试题广场 >

在下列几种排序方法中,空间复杂度最高的是()

[单选题]
在下列几种排序方法中,空间复杂度最高的是()
  • 归并排序
  • 快速排序
  • 插入排序
  • 选择排序
快速、插入、选择都是o(1),归并排序是o(n),因为他在合并两个排好序的子序列的过程中需要新的空间来存储数据
发表于 2017-03-04 16:51:47 回复(0)
快速排序的空间复杂度到底是多少?O(nlogn)、O(n)?
发表于 2017-03-02 16:15:42 回复(5)
A归并排序,空间复杂度O(n),插入和选择排序空间复杂度均为O(1),快速排序空间复杂度O(nlogn)。
发表于 2017-01-23 16:58:29 回复(0)

常见算法复杂度比较


序号


排序类别


时间复杂度


空间复杂度


稳定


1


插入排序


O(n2)


1



2


希尔排序


O(n2)


1


×


3


冒泡排序


O(n2)


1



4


选择排序


O(n2)


1


×


5


快速排序


O(Nlogn)


O(logn)


×


6


堆排序


O(Nlogn)


1


×


7


归并排序


O(Nlogn)


O(n)




发表于 2017-03-23 09:05:46 回复(0)
空间复杂度最大的是归并排序O(n
然后是快排空间复杂度O(log2n 
其余包括冒泡、简单选择、直接插入、希尔、堆、基数空间复杂度都是O(1)
发表于 2020-06-19 08:28:53 回复(0)
发表于 2019-06-22 10:16:05 回复(1)