你如何理解空间复杂度？请说明快速排序的空间复杂度以及最坏情况的空间复杂度是多少？

回答思路

1. 正确解释空间复杂度衡量算法运行所需的额外内存
2. 指出快速排序平均空间复杂度为 O(log n)
3. 指出最坏情况空间复杂度为 O(n) 并解释原因