快速排序 占用堆栈空间有关问题

快速排序 占用堆栈空间问题
在算法导论书上看到，将快速排序改成如下：

C/C++ code

void quick_sort4(int *A,int l,int r){    while (l<r)    {        int m=partition3(A,l,r);        if (m<=(l-r+1)/2)        {            quick_sort4(A,l,m);            l=m+1;        }        else        {            quick_sort4(A,m+1,r);            r=m;        }    }}

也就是说，每次只递归最小的那个数组，则可以将快速排序的空间复杂度控制在O(lgn)
这个怎么理解，怎么证明空间复杂度控制在了O（lgn）呀？



[解决办法]
递归过程中每一层参数传递占用的空间都为常数（只有三个参数），那么整个算法的空间复杂度就只与递归/堆栈深度有关系。
假设真象你说的那样，每次只递归较小的那个数组，递归表达式是这样的：
T(n)=T(m)+O(n) <= T(n/2)+O(n)，这里m<=n/2
很显然递归层数<=lgn

第一.你的代码明显有问题，m<=(l-r+1)/2 ？应该是m<=(r-l+1)/2吧。
第二.没有给出partition3的具体实现过程（个人猜测这个函数的功能是将原数组划分成两个的同时也完成了对那个较大数组的排序），因此对整个算法的正确性表示怀疑。

大家可能没看过《算法导论》，即便看过了手边也没书，可能早不记得你说的是什么了。这样发问很难让别人作答。

查看更多 下一篇