从递归视角理解快速排序（C语言实现）

1. 在说快速排序之前我们先要了解递归。

递归，按照通俗易懂的理解就是自我调用。写一个自我调用的函数如下：

int defined_pow(int n,int count)
{
	if(count == 0)
		return 1;
	else
		return n*defined_pow(n,count -1);
 } 

这个函数的作用是求n的count次方，当count为0时，我们返回1（任何数的0次方都等于1），当count不为0时，我们先计算n的count-1次方，再讲结果与n相乘，再返回给调用它的函数。
这个函数会一直调用它自己，每次将结果多乘一个n，计数器count减少1。当count等于1的时候，n总共被乘了 count次，n^count*1，刚好是n的count次方。

---

通常在递归的函数中，会设置一个if语句，if语句控制递归结束的条件（否则就陷入死循环），上一个例子中，我们设置的递归结束条件是count==0，即计数器等于零。而在下面出场的快速排序算法中，我们设置的条件则是所要排序的数组的左下标大于等于右下标。

2. 先来讲一下快速排序的思想：
   快速排序（从小到大），指的是将数组中的第一个数base作为参考，将所有大于第一个数的元素放到第一个数的右边，同时将所有小于第一个数的元素放到第一个数的右边。这样，第一个数base就不再是数组中的第一个元素，而是被存放在了数组的中间。
   此时我们再分别在base的左边和base的右边调用这个快速排序函数本身，以base为分界线，分别将base左边和base右边的数组进行递归，下标low和high分别表示最左边的元素下标和最右边的元素下标，使得比它们大的数都被存放在它们各自的右边，比它们小的数都被存放在它们各自的右边。
   在左下标大于等于右下标之前，函数会一致递归调用它本身，最后的结果是对于数组中所有的数，都有：1.它左边的数小于它本身；2.它右边的数大于它本身（此时递归调用已经将区间缩小到。
   上代码：

void QuickSort(int a[],int low, int high)
{
	if(low>=high)
		return;
	int i,j,base,temp;
	i = low,j = high;
	base = a[low];
	
	while(i < j)
	{
		while(i < j && a[j] >= base)
		{
			j--;
		}
		while(i < j && a[i] <= base)
		{
			i++;
		}
		if(i < j)
		{
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	
	a[low] = a[i];
	a[i] = base;
	
	QuickSort(a,low,j -1);
	QuickSort(a,j + 1,high);	
}

在代码中，while循环的作用主要是将右边小于base的数与左边大于base的数的位置互换，还没有将数组的第一个元素插入到小于它的数与大于它的数之间。
循环结束后，i的值实际上已经等于j的值，此时将数组第一个元素的值与第i个元素的值交换，就能够确保第i个元素左边的数都小于它，第i个元素右边的数都大于它。
使用如下主函数调用QuickSort（主函数中generateArray是生成元素总数为count的数组，printArray是从头到尾打印数组元素）：

main()
{
	int n;
	printf("请输入数组长度：");
	scanf("%d",&n);
	
	int arr[n];
	generateArray(arr,n);
	printArray(arr,n);
	QuickSort(arr,0,n);
	printArray(arr,n);
}

运行，输入9，得到如下结果：

第0个数为：79
第1个数为：27
第2个数为：2
第3个数为：0
第4个数为：28
第5个数为：9
第6个数为：89
第7个数为：71
第8个数为：64

---排序后---
第0个数为：0
第1个数为：2
第2个数为：9
第3个数为：27
第4个数为：28
第5个数为：64
第6个数为：71
第7个数为：79
第8个数为：89