在对n个元素进行快速排序的过程中，平均情况下的空间复杂性为（）

在快速排序的非递归算法中，可引进一个栈。这个栈的大小由递归调用的深度决定，最多不会超过n，如果每次都要选较大的部分进栈，处理较短的部分，深度最多不超过log₂n。也就是说，快速排序需要的附加存储开销为O(log₂n)。可以证明平均比较次数是O(n log₂n)。