快速排序--全集

快速排序：一听名字就知道这种排序很快的，是吧？没错，它是一种效率比较高的排序算法。

快速排序采用的是分治的思想。

比如，将一串数中的一个元素作为基准，然后将比它小的数排在它的左边，比它大的数排在它的右边。将作为基准的那个元素排在正确的位置。然后通过递归，依次将所有的元素都排好。（实质就是递归子问题）

在这里，快速排序也有几种不同的方式，下面我给大家一一叙述吧。

快速排序的几种方法：

1.左右指针法(交换)：
       有一个数组a[size],左指针left指向下标为0的位置，右指针right指向下标为size-1的位置，同时标志key=a[right];left找a[left]>key的元素的下标，right找a[right] < key的元素的下标。left先开始走，当遇到比key大的数时，停下来，再由right开始走，当遇到比key小的数时，停下来。将left和right分别指的数交换，前提是left<right时，如果left>=right就说明一次快排结束。再将left指向的值与key值交换即可。此时的数组呈现出左边的值都比key值小，右边的值都比key值大。一次快排将数组分为两个区间，我们再对每个区间进行上述的排序方式。直到每个小区间已不能再划分。(即一个区间只有两个元素)

代码实现：

int PartSort(int* a,int left,int right)
{
	int& key = a[right];
	//int key = right;
	while(left < right) 
	{
		while(left < right && a[left] <= key) //a[left] <= a[key]
			++left;
		while(left < right && a[right] >= key) //a[right] >= a[key]
			--right;
		swap(a[left],a[right]);
	}
	swap(a[left],key);
	//swap(a[left],a[key]);
	return left;
}
void QuickSort(int* a,int left,int right)
{
	if(left < right)