C-快速排序的空间复杂度O（logn）~O（n），为什么？

Question

快速排序的空间复杂度O（logn）~O（n），为什么？谁能告诉我。。。

Answer 1

快速排序复杂度分析

Answer 2

我的算法不是很好, 说一下我的理解, 且作抛砖引玉.

快排的空间消耗主要在递归的堆栈上(partition中的pivot变量可以重复使用):

申明全局数组a
quicksort(left, right)
if right > left
mid = partition(left, right) //分割
quicksort(left， mid) //递归前半部分
quicksort(mid, right) //递归后半部分

用自己的栈来实现, 可能看的更清楚些:

申明全局数组a，
申明全局栈stack
procedure quicksort()
stack.push([0,a.length-1]);
while true
[left, right]=stack.pop()
break if left > right
mid=patition(left, right)
stack.push(left, mid);
stack.push(mid, right);

对上述算法, 每一次while循环, 设进入前栈大小为x,

 变化为:
如果到达子节点, break, 循环退出, 栈为x-1;
否则循环退出时,栈为x+1

具体来看栈的大小：

 开始: 1
第一层，1 -> 0 -> 2;
第二层，2 -> 1 -> 3
第三层, 3 -> 2 -> 4
第四层, 4 -> 3 -> 5
..
第m层, m -> m-1 -> m+1

第n层到达叶节点, 那么:
第n层, n -> n-1
回到n-1层,
若另一个节点也为叶节点
n-1 -> n-2
回到n-2层;
若另一个节点不为叶节点
n-1 -> n-2 -> n
进入第n层

可见, 栈的大小基本上等于 当前层次;
对递归树来说, 最大栈大小 之和 树的高度相关.
快排 递归树,最好情况下是一个比较平衡的树, 高度为O(lg n); 最坏情况下, 树的高度为为O(n)