n个记录的文件进行快速排序,所需要的辅助存储空间为()。A.O(1)B.O(log2n)C.O(n)D.O(n2)

Question

n个记录的文件进行快速排序，所需要的辅助存储空间为( )。

A．O(1)

B．O(log2n)

C．O(n)

D．O(n2)

Answer 1

正确答案：B
解析：快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log₂n，所以其空间复杂度为O(log₂n)。