快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

时间复杂度为O(n*logn)

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

参考博客：http://blog.csdn.net/morewindows/article/details/6684558

下面给出的是一种以左端点为基点的快速排序，此种方法最坏情况时间复杂度会达到O(n^2)，这种情况是给定的数组里面的是完全是倒序排列。

对于ACM竞赛采用此种方法可能会又出现卡数据的现象，即超时。这是时间复杂度可能是O(n^2)。而algorithm头文件下的sort是经过多种优化后的快速排序。但是对于适合下面这种quick_sort排序的sort反而会慢了一点。

参考落谷的一道考排序的题：https://www.luogu.org/problemnew/show/P1177

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000+7;

int n;
int a[MAXN];
void quick_sort(int *a, int l, int r)
{
	if(l < r)
	{
		int i = l, j = r;
//		int mid = (l + r) / 2;
//		swap(a[mid], a[l]);      // 若选择中间点为基点，加上这两行即可
		int num = a[l];			// 选择左端点为基点
		while(i < j)
		{
			while(i < j && a[j] >= num)	// 先从又往左找
				j--;
			if(i < j)
				a[i++] = a[j];
			while(i < j && a[i] < num)	// 再从左往右找
				i++;
			if(i < j)
				a[j--] = a[i];
		}
		a[i] = num;
		quick_sort(a, l, i-1);		// 分治
		quick_sort(a, i+1, r);		//
	}
}
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		for(int i=0; i<n; i++)
			scanf("%d", &a[i]);
		quick_sort(a, 0, n-1);
		printf("%d", a[0]);
		for(int i=1; i<n; i++)
			printf(" %d", a[i]);
		printf("\n");
	}

	return 0;
}