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

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

 1

#include<iostream>
 2

 3

using namespace std;
 4

 5

void QuickSort(int [],const int,const int);
 6

int Partition(int [],const int,const int);            
 7

 8

 9

int 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

30

int 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

58

void 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 的情况，一切正常。

　  结束，将中间值和 j 互换，返回 j 的值，也看似没问题，假设最后还有两个元素来进行Partition，它们在做完开始和中间的那段之后顺序已经排好了，这个时候再swap，那么就又乱了，所以说，得加上一个判断，if( array[front] > array[j])，在进行互换。当然还有另外一种解决方法，那就是在中间的那段修改，使得当顺序正确的时候，j 的值等于 front，大家自己想下怎么改代码吧。