试题-下列四种排序中()的空间复杂度最大

题目

下列四种排序中()的空间复杂度最大

A.快速排序

B.冒泡排序

C.希尔排序

D.堆

解答

正确答案是 A

快速排序，正常为O(log2n)，这也是递归的深度，如果基准值选择不好为O(n)，当然，即使非递归结果也是如此

冒泡排序属于简单排序，只需要几个辅助循环变量，因此为O(1)
希尔排序，只是将直接插入排序进行修改，一般不设置特别的缩小增量序列，也是O(1)

堆排序，只需要一个中间用辅助变量和一些循环变量，也是O(1)

C 3条回复评论

小小精灵

快速排序有递归深度的空间，归并O(N)

发表于 2018-10-13 11:14:14

虹猫

时间和空间是矛盾的，时间好的算法，空间就不会太好，并归和快排时间好，空间就花的多

发表于 2018-10-13 11:14:04

窦先生

快速排序需要用到递归，递归本身就是耗内存的，对于快速排序一般空间复杂度O(Nlogn)

发表于 2018-10-13 11:13:54