<center>

问题 : 快速排序

</center>

题目描述

快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排序的记录分割成两个独立的部分，其中一部分记录的关键字均比另一部分的关键字小，在分成两个部分之后则可以分别对这两个部分继续进行排序，从而使整个序列有序。
快速排序的算法可以描述如下：
在本题中，读入一串整数，将其使用以上描述的快速排序的方法从小到大排序，并输出。

输入

输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过100000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。

输出

只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。

样例输入

102 8 4 6 1 10 7 3 5 9

样例输出

1 2 3 4 5 6 7 8 9 10

提示


在本题中，需要按照题目描述中的算法完成快速排序的算法。


快速排序是一种十分常用的排序算法，其平均时间复杂度为O(kn lnn)，其中n为待排序序列中记录的个数，k为常数。大量的实际应用证明，在所有同数量级的此类排序算法中，快速排序的常数因子k是最小的，因此，就平均时间而言，快速排序是目前被认为最好的一种内部排序方法。


而在C语言的常用编译器中，qsort函数是一个非常常用的快速排序函数。


快速排序思想：

对于一组数列，先找序列中第一个数为基准x，将序列中的数比x大的放到x的右边，比x小的放到x左边；再将x放到中间。在利用递归进行排x左边和x右边的子序列。直到把所有的序列都放对位置。（找到基准x后分别从头和从未开始找，直到左边找到一个比x大的值，右边找到一个比x小的值，且左边位置小于右边位置；然后交换两个值。再继续找；直到左边位置与右边位置相等结束循环。再将相等位置的值与基准交换。即完成一次，再分别将基准左右两边的子序列同理排序，直到最后整的序列排完）

代码如下：

#include<stdio.h>
void quicksort(int left,int right);
int a[100010];
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		quicksort(1,n);
		for(i=1;i<=n;i++)
			printf("%d ",a[i]);
		printf("\n");
	}
	return 0;
}
void quicksort(int left,int right)//快速排序核心代码
{
	int i,j,t,x;
	if(left>right)
		return;
	
	i=left;
	j=right;
	x=a[left];
	
	while(i!=j)
	{
		while(a[j]>=x&&i<j)//如果基准右边比基准大直接查找下一个位置，直到找到比基准小的值
			j--;
		while(a[i]<=x&&i<j)//如果基准左边比基准小直接查找下一个位置，直到找到比基准大的值
	                i++;
		if(i<j)//交换
		{
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}
        //基准与相同位置的值互换
        a[left]=a[i];
	a[i]=x;
	
        //递归分别排基准左边和右边的子序列
	quicksort(left,i-1);
	quicksort(i+1,right);
	
	return;
}