Recursive to Nonrecursive
看了下小炒肉大神的代码，然后好像理解怎么讲递归代码转非递归了，函数体被N次递归划分成3块，然后用3个状态变量来区分当前层是在哪一个状态，top返回reference恰好可以完成这个任务，也即压站之后，还可以修改top的type的属性，然后每一块要处理相应的参数，然后压站，其实也就是自己写了一下系统的函数调用栈的代码
下了一下Qsort的非递归，以及DrawLine的代码
#include <iostream>
#include <stack>
using namespace std;
struct Info
{
int low, high;
int type;
//Info generate();
};
/*
Info Info::generate()
{
int mid=partition(a, low, high);
if(type==0)
{
type++;
return {low, mid-1, 0};
}
else
{
type++;
return {mid+1,high,0};
}
} */
int partition(int *a, int low, int high)
{
int pivot=a[low],i=low;
for(int j=low+1;j<=high;j++)
{
if(a[j]<pivot)//[low,i]:<pivot, [i+1,j-1]: >=pivot
{
swap(a[++i],a[j]);
}
}
swap(a[i],a[low]);
return i;
}
void Qsort(int *a, int low, int high)
{
if(low<high)
{
int mid=partition(a, low, high);
Qsort(a,low, mid-1);
Qsort(a,mid+1, high);
}
else
;
}
void Qsort_nonrecursive(int *a, int low, int high)
{
stack<Info> S;
S.push({low, high, 0});
while(!S.empty())
{
Info &cur=S.top();
if(cur.low<cur.high)
{
int mid=partition(a,cur.low, cur.high);
if(cur.type==0)
cur.type++,S.push({cur.low,mid-1,0});
else if(cur.type==1)
cur.type++,S.push({mid+1,cur.high,0});
else
S.pop();
}
else
{
S.pop();
}
}
}
/*
void Qsort_nonrecursive1(int* a, int low, int high)
{
stack<Info> S;
S.push({low, high});
while(!S.empty())
{
Info &cur=S.top();
if(cur.low<cur.high)
{
S.push(cur.generate());
}
else
{
S.pop();
while(!S.empty())
S.pop();
}
}
}
*/
void Show(int *a ,int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
int main()
{
int a[]={2,3,4,523,4,5,345,4,4,24,4,4,1,1,1,1,325,246,537,346};
int n=sizeof(a)/sizeof(int);
Qsort_nonrecursive(a, 0,n-1);
Show(a, n);
return 0;
}
另外今天对于递归算法的时间复杂度计算，阮师兄大神建议背下主定理，因为之前总是怕过一段时间忘了，还是习惯自己plugin的方法带入计算，这个我后来看了下也不是很容易忘记，可以提高效率。算导的可读性绝对完爆国内那些填鸭式不易记忆的教材
T(n)=aT(n/b)+f(n)
如果f(n)多项式上大于n^(logb a), 或者小于, 取两者较大的。例如f(n)=O(n^(logb a-epsilon)),epsilon>0, 那么T(n)=O(logb a);
如果多项式上相等的话，则是T(n)=f(n)*lg n;