递归算法转非递归&快速排序

将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。

1. 直接转换法

直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。

尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：

long fact(int n)

{

　　if (n==0) return 1;

　　else return n*fact(n-1);

}

当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：

long fact(int n)

{

　　int s=0;

　　for (int i=1; i<=n;i++)

　　s=s*i; //用s保存中间结果

　　return s;

}

单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下：

int f(int n)

{

　　if (n= =1 | | n= =0) return 1;

　　else return f(n-1)+f(n-2);

}

对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1和s2保存中间的计算结果，非递归函数如下：

int f(int n)

{

　　int i, s;

　　int s1=1, s2=1;

　　for (i=3; i<=n; ++i)

        {

　　       s=s1+s2;

　　       s2=s1; // 保存f(n-2)的值

　　       s1=s; //保存f(n-1)的值

　　}

　　return s;

}

2. 间接转换法

该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下：

将初始状态s0进栈

while (栈不为空)

{

　　退栈，将栈顶元素赋给s;

　　if (s是要找的结果) 返回;

　　else

        {

　　    寻找到s的相关状态s1;

　　    将s1进栈

　　}

}

间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等。

使用非递归方式实现递归问题的算法程序,不仅可以节省存储空间,而且可以极大地提高算法程序的执行效率【这个不是固定逻辑】

由于本人学习的是《严蔚敏数据结构》

找了网上的非递归逻辑

严蔚敏数据结构:

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)
{
visit(p->data);
push(S,p->lchild);
} //向左走到尽头
pop(S,p);
if(!StackEmpty(S))
{
pop(S,p);
push(S,p->rchild); //向右一步
}
}//while
}//PreOrder_Nonrecursive

按照上面写了非递归的，结果死循环了，错误代码如下:

自己刚开始整的，用了栈，没发现自己递归调用了，^_^

/**
	 * 这都是自己编写^_^
	 * 多余出了栈
	 * @param node
	 */
	public void traversePreOrderByStack(Node<E> node) {
		Stack<Node<E>> stack=new Stack<>();
		stack.push(node);
		while (!stack.isEmpty()) {
			Node<E>temp=stack.pop();//这里一压一如没啥，但也没有bug
			System.out.println(temp.value);
			if (temp.left!=null) {
				Node<E> left=temp.left;
				traversePreOrderByStack(left);
			}
			if (temp.right!=null) {
				Node<E> right=temp.right;
				traversePreOrderByStack(right);
			}
		}
	}
	

	/**
	 * 根据常规的栈使用方式改造的
	 * @param node
	 */
	public void traversePreOrderByStack1(Node<E> node) {
		Stack<Node<E>> stack=new Stack<>();
		stack.push(node);
		while (!stack.isEmpty()) {
			Node<E>temp=stack.pop();
			System.out.println(temp.value);
			if (temp.left==null) {
				return ;
			}else {
				traversePreOrderByStack1(temp.left);
				if (temp.right==null) {//其实和上一个逻辑结构是一样的
					return;
				}else {
					traversePreOrderByStack1(temp.right);
				}
			}
			
		}
	}

/**
	 * 看了网上正确的，还是无法深的要领，结果死循环了
	 * @param node
	 */
	public void traverseInorderByStack1(Node<E> node) {
		Stack<Node<E>> stack = new Stack<>();
		Node<E> p = node;
		stack.push(p);
		while (p != null || !stack.isEmpty()) {
			Node<E> qNode=p;
			p = stack.pop();
			if (qNode!=p) {
				System.out.println(p.value);
				if (p.right != null) {
					stack.push(p.right);
				}
				
				if (p.left != null) {
					stack.push(p);
					p = p.left;
				}
			}
		}
	}

正确的方法一：

/**
	 * 在遍历左子节点前，保存右节点的信息
	 * 
	 * @param node
	 */
	public void traverseInorderByStack2(Node<E> node) {
		Stack<Node<E>> stack = new Stack<>();
		Node<E> p = node;
		stack.push(p);
		while (!stack.isEmpty()) {
			p = stack.pop();
			System.out.println(p.value);
			if (p.right != null) {
				stack.push(p.right);
			}
			if (p.left != null) {
				stack.push(p.left);//压进左子节点，然后通过这个栈的死循环出栈得到下个逻辑循环
			}

		}
	}

快速排序

在项目用户不是很大，却老在面试的时候被问及

快速排序的基本思想是

1、先从数列中取出一个数作为基准数

2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3、再对左右区间重复第二步，直到各区间只有一个数

概括来说为 挖坑填数+分治法

下面举例来进行说明，主要有三个参数，i为区间的开始地址，j为区间的结束地址，X为当前的开始的值

第一步，i=0,j=9,X=21

0	1	2	3	4	5	6	7	8	9
21	32	43	98	54	45	23	4	66	86

第二步，从j开始由，后向前找，找到比X小的第一个数a[7]=4,此时i=0,j=6,X=21 
进行替换

0	1	2	3	4	5	6	7	8	9
4	32	43	98	54	45	23	21	66	86

第三步，由前往后找，找到比X大的第一个数a[1]=32,此时i=2,j=6,X=21

0	1	2	3	4	5	6	7	8	9
4	21	43	98	54	45	23	32	66	86

第四步，从j=6开始由，由后向前找，找到比X小的第一个数a[0]=4,此时i=2,j=0,X=21，发现j<=i,所以第一回结束

可以发现21前面的数字都比21小，后面的数字都比21大 
接下来对两个子区间[0,0]和[2,9]重复上面的操作即可

下面直接给出过程，就步详细解说了

i=2,j=6,X=43

0	1	2	3	4	5	6	7	8	9
4	21	43	98	54	45	23	32	66	86

i=4,j=6,X=43

0	1	2	3	4	5	6	7	8	9
4	21	32	98	54	45	23	43	66	86

i=4,j=5,x=43

0	1	2	3	4	5	6	7	8	9
4	21	32	43	54	45	23	98	66	86

i=5,j=5,x=43

0	1	2	3	4	5	6	7	8	9
4	21	32	23	43	45	54	98	66	86

然后被分为了两个子区间[2,3]和[5,9]

….最后排序下去就是最终的答案

0	1	2	3	4	5	6	7	8	9
4	21	23	32	43	45	54	66	86	98

总结：

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。