C++ 递归函数的详解

说到递归函数，就会想起递归的快速排序。

1.快速排序是什么呢？

快速排序的基本思想是：通过一趟快速排序，把待排记录分成两
个子序列，其中一个子系列中的记录都小于另一个子序列，然后，
分别对两个子序列进行快速排序。 
可以看出，快速排序的核心就是划分子序列。

2.下面让我们了解一下递归函数快速排序的思想：

（1）将待排序的数据放入某数组中（如数组a[]） 中，下标从 low 到 high；

（2）对数组进行如下操作：从数组中取一个元素值作为枢轴

记录（一般取第 0 号元素，即 a[0]），存入 key（一个变量） 中；

（3）在数组 a 中，将 key 调整到适当位置，然后将比 key 
大的元素都放在 key 的右边，比 key 小的数都放在 key 
的左边。

（4）这一趟排序的结果是key 将原数组 a 分割成
了两个子数组，key 的左边的值都比key 小，右边的都比 
key 大。

（5）此时，问题就成了如何都将这两个子数组进行排序的问题，显然
对这两个子数组调用上述方法即可，即进行递归调用上述方法，
直到排序完成。

（6）显然，通过上述过程，当我们处理完所有的元素时，最终结果
为：每个元素的左边的元素都不大于该元素，而右边的元素都不小
于该元素。

3.如何确定key的位置呢？

我们确定key的值后，利用 key 将数组 a 划分成两个子数组。

具体方法：

（1）取出数组的第 0 个元素，作为分界值放到 key 里，
即 key = a[0]; 此时，数组元素 a[0] 空闲，用一个左探针left
指示，即 left = 0；
（2）利用右探针 right 从右往左走，寻找小于 key 的元素，找到
后就将该元素的值放进 left 所指示的空闲位置，此时 right 所
指示位置成为空闲位置；
（3）让左探针 left 往右走，寻找比 key 大的元素，找到则将该
元素的值放进 right 所指示的空闲位置。此时 left 所指示位置
变为空闲；
（4）循环执行 2、3步，直到 right 不再大于 left为止（此时，
意味着将所有元素都与 key 进行了比较）。left 与 right 相遇的
地方就是 key 的位置。

具体的代码：

#include   <stdio.h>

void QuickSort( int a[],  int low,  int high);
void main() 
{
int a[] = { 32, 8, 65, 18, 19, 12, 61 };
int i;
 
QuickSort(a, 0, 6);
 
for(i=0; i<7; i++)
printf("%4d", a[i]);
}

//QuickSort方法，实现函数的快速排序

void QuickSort( int a[],  int low,  int high)
{    
int key;
     int left, right;
     // 若待排序列为空或仅有一个元素，则无需排序
     if( low >= high )  return ;
      // 1  将待排记录划分成两个子序列
     // 1.1  选择序列中第一元素作为轴记录
     key = a[low];
     // 1.2  根据轴记录 key 将待排序列划分成两个子序列
     left = low; 
right = high;

while( left < right ) 
{
   while( left<right && a[right] >= key) 
right--; // right从后向前扫描，跳过"大"的元素
   a[left] = a[right];      //   遇到"小"元素，移动到前面去
   while( left<right && a[left] <= key) 
left++; //left 从前向后扫描，跳过小于轴记录的元素
   a[right] = a[left];       //   遇到"大"元素，移动到后面去
}
    //   1.3  放置轴记录
    a[left] = key;
    // 2.对两个子序列分别进行快速排序
    QuickSort(a, low, left-1);
    QuickSort(a, left+1, high);
}