rambo

排序算法（三）快速排序提高

2015年2月10日 BLOG 0 Comments

尾递归思想：

快速排序的栈深度（尾递归）

QUICKSORT算法的递归版本包含了两个对其自身的递归调用。在调用PARTION后，QUICKSORT又递归调用左边的子数组和右边的子数组。QUICKSORT的第二次递归调用不是必须的，可以用迭代结构来代替它，这种技术称为尾递归。大多数编译程序都加以采用。

QQ截图20150909004856

编译器通常使用栈来存储递归执行过程中的相关信息，包括每一次递归调用的参数等。最新调用的信息存在栈的顶部，而第一次调用的信息存在栈的地步。当一个过程被调用时，其相关信息被压栈；当它结束时，其信息被弹出。假设数组参数是用指针来指示的，所以每次过程调用只需O(1)的栈空间。栈深度是在一次计算中会使用的栈空间的最大值。

1
2
3
4
5
6
7
8
9
10
void quickSort(SqList * list , int low ,int high){
　　int pivot;
　　while(low<high){
　　     pivot=Partition(list,low,high);
　　     quickSort(list, low,high);
　　     //quickSort(list,low,pivot-1); 原递归调用
　　     //quickSort(list,pivot+1,high);
　　     low = pivot+1; /*尾递归*/
　　}
}

首先：尾递归是线性递归的子集，属于线性递归。
其次，上文所举的第二个例子中在TailRescuvie(n-1, 1)没有计算出来之前，是不能return的。也就是说递归过程和第一个例子是差不多的，根本没有节约资源，甚至更浪费。其实，编译器会很容易的对尾递归使用跳转语句进行优化，其实是可以return的。
尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题——因为参数里带有前面若干步的运算路径。对于阶乘而言，越深并不意味着越复杂。从时间和空间效率上看，尾递归和传统递归差不多。递归运算效率低主要是分支巨大，像阶乘这类单分支的递归，效率并不低。递归运算的深度和运算总量大致成指数关系，return多次并不会造成显著的性能损失。
一言以蔽之，传统递归越深，距离目标越近；尾递归越深，距离起点越远。尾递归适用于运算对当前递归路径有依赖的问题，传统递归适用于运算对更深层递归有依赖的问题。

 

参考资料：

1）http://bbs.csdn.net/topics/390215312