从快速排序来看迭代和递归的区别

先贴一个有逻辑问题的快速排序：

 1#include<iostream>
 2
 3using namespace std;
 4
 5void QuickSort(int [],const int,const int);
 6int Partition(int [],const int,const int);            
 7
 8
 9int main()
10{    
11    int arr[10] = {12,14,8,4,9,15,3,11,25,99};
12    
13    for(int i = 0;i <= 9; i++)
14    {
15        cout << arr[i] << "  ";
16    }
17    cout << endl;
18
19    QuickSort(arr,0,9);
20
21    for(i = 0;i <= 9; i++)
22    {
23        cout << arr[i] << "  ";
24    }
25    cout << endl;
26
27    return 0;
28}
29
30int Partition(int array[],const int front,const int end)
31{
32    int refer = array[front];
33    int i = front + 1;
34    int j = end;
35
36    while(i < j)
37    {
38        while(refer > array[i] && i < end) i++;
39        while(refer <= array[j]&& j > front) j--;
40
41        if(i < j)
42        {
43            cout << array[i] << " & " << array [j] << "\n";
44            std::swap(array[i],array[j]);
45        }
46
47    }
48    
49
50    std::swap(array[front],array[j]);
51
52    
53    return j;
54
55}
56
57
58void QuickSort(int array[],const int front,const int end)
59{
60    if(front < end)
61    {
62        int part = Partition(array,front,end);
63        QuickSort(array,front,part);
64        QuickSort(array,part, end);
65    }
66
67}

上面所写的这个快速排序中，分别用到了迭代和递归两种方法，其中，QuickSort函数就是递归，Partition则是迭代。下面我们就来看下递归和迭代的异同：

　　1. 对于迭代和递归都是用循环结构，迭代则是显示的使用循环，上面的Partition函数就是显示的使用了while 循环，而递归则是重复性的函数自身调用（可以是间接的也可以是直接的）来实现循环，QuickSort函数就是直接的调用自身来实现循环。

　　2. 它们循环的结束方式也各不相同，对于迭代，不符合循环条件时迭代就结束了，Partition函数中，当i >= j 的时候，迭代就结束了；而对于递归，则是当不满足基础条件或者满足结束条件时候，递归结束，对于QuickSort函数，当 front >= end 的时候,递归就结束了。

　　3. 对于迭代，其实解决问题的方法是不断的修改迭代变量的值，直到碰到令循环失败的迭代变量；递归则是，不断产生原始问题的简化副本，直到问题简单到基本情况。

　　4. 递归使用重复调用函数的机制，不断为程序申请栈空间以存放函数数据，使算法的时间和空间复杂度很大，而迭代则是在循环体内部进行的，就避免了使用递归带来的问题。从理论上来讲，能使用递归解决的问题，就能使用迭代来解决。但是我们之所以还在使用递归，使用递归更能反应出问题，并令程序更容易理解和调试。而使用迭代的时候，程序逻辑不是很直观。

　　

　　对于前面三点，还是很容易理解的。第四点，我们就从这个程序来说明：

　　QuickSort所做的工作是在front不小于end的情况下，一直调用自身压栈，了解程序运作的应该这个，每次压栈都CPU都需要处理函数的一些信息，并将这些信息写入程序栈中，但从一次入栈出栈来说，这样的代价不是很高，但是使用递归，所要循环的次数有的时候是非常大的，这就变成了一个不小的开销。

 

但是用递归写的算法相当明了，用迭代却要花费点时间来了解程序逻辑结构，下面就来改正程序的错误：

　　首先是递归函数QuickSort的问题，可以很直观的看到，其在迭代的时候把已经确定好的元素也重复做排序了，这是没有必要的，所以在递归的时候调用的part要加减一位。

　　再来看迭代函数Partition的问题，我第一次看这个函数看了很久也没看出问题之所在，经过一个比较系统的分析的之后才看问题的所在，把这个函数分成三个状态：开始、中间和结束。

　　　　开始，选择的中间值，i和j的值都合理。排除

　　　　中间，所比较的符号也没有问题，注意到了在 while 循环的中 i 和 j 可能出现 i > j 的情况，一切正常。