快速排序（递归）

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

下面通过图解的形式来帮助理解：

图中的key便是基准值对应的下标，L和R分别是左边和右边的下标，在下面那个图解里是实现升序，基本步骤就是先让R走，R需要找比key对应的数小的数，只要大于就一直往前走，直到找到小的或者跟L相遇就停下来；然后是L走，它要找到比key对应的数大的数，直到找到或者跟R相遇就停下来。

从上图中我们可以看到，L和R一直走，总会相遇，相遇后，将key对应的数与相遇处的数交换，并将key（基准值下标）置为相遇处的下标，因为此时相遇处的数是 已经排在了它对应的位置的，即左边的数都比它小，右边的数都比它大。然后，我们用递归，再将key左边部分的数和右边部分的数进行排序。

快速排序的大概思路就是这样啦，接下来我们上代码。

void QuickSort(int* a, int left, int right)
{
	//只有一个元素或者不存在
	if (left >= right)
		return;

	//保存起始位置和末尾位置
	int begin = left, end = right;

	int key = left;  //key为起始位置
	
	while (left < right)
	{
		//右边先走
		//注意left < right这个条件，在自增过程中left可能一直加，加到超过right
		while (left < right && a[right] >= a[key])
		{
			right--;
		}

		while (left < right && a[left] <= a[key])
		{
			left++;
		}

		swap(&a[left], &a[right]);
	}

	//出循环后，left = right
	//交换相遇点处的数据和key对应的数据，此时右侧数据大于a[key],左侧小于a[key]
	swap(&a[key], &a[left]);  //交换后a[key]就排好了，在正确的位置

	key = left;

	//递归，排a[key]左侧和右侧的数据
	//排左边
	QuickSort(a, begin, key - 1);

	//排右边
	QuickSort(a, key + 1, end);
}

我们来画一下递归展开图帮助理解：