数据结构 排序算法性能比较

Question

下列排序算法中，平均时间复杂度为O(nlogn)且占用额外空间最多的是( C )。A. 堆排序 B. 插入排序 C. 归并排序 D. 快速排序我选的是C ，注意：问的是占空间最多的 我搜了一下下面的资料，在此问问大家，看看C对不对 ？

Answer 1

首先各种不同的数量级，存在如下关系：
O(1)<O(log2n)<O(n)<O(n*log2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)
然后就知道了，空间复杂度，归并 > 快速 > 堆
注：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
因此C是对的。