快速排序
是非常经典的一个算法，可以在对数规模的时间下实现对一组数的排序。
其基于分治的思想，每一趟排序把原组数划分为更小的范围进行排序，并且一定有一个数会在每趟排序下放在最终的位置。
对于一个数组arr[p....r]进行快排：
划分：把数组划分为arr[p...q-1]，arr[q]，和arr[q+1...r]；其中，arr[p...q-1]的元素都比arr[q]小，和arr[q+1...r]中的元素都比arr[q]大。
解决：递归调用快排函数，对于子数组进行排序。
合并：由于子数组是原址排序，并不需要合并操作。所以一系列的递归调用结束以后原数组arr[p....r]已经有序。
每次选取一个元素x作为主元素（pivot element），围绕这个主元素对数组进行排序。
快速排序的算法效率与输入有关，当输入的数组元素为完全有序时快排效率最低，时间复杂度达到O(n²)
而一般的，快速排序算法的平均运行时间接近于其最好的情况O(nlgn)
算法导论上对这个结论的这个证明比较神奇，有空的话值得一看。
算法导论上的遍历方法和我这里写的方法不太一样，但是其分治的思想是一样的。
下面我尝试用通俗的语言描述我所写的快排这个过程。
从这一个分组的两头开始向中间遍历，一边遍历一边把大的放到右边，小的放到左边。
最后当low=high时停留在pivot的位置，再将一开始枢纽pivot的元素塞回去。
枢纽元素pivot最后所在的位置为其最终位置，最后以枢纽元素为中心把大分组的元素划分为两部分
递归调用快排函数，对于更小的部分继续排序、划分、再对更小的分组进行快排，再划分……
注：pivot的选取是任意的，这里为了方便每次选取最左元素作为枢纽。实际上每次如果选取的枢纽在一趟排序后恰能把这一组数据从中间划分为两部分最佳。
（一趟排序后pivot左边的元素不一定有序，但比pivot元素小（<=）；pivot右边的元素也同理，不一定有序，但比pivot元素大。（>=））
对于快排算法我一开始学习也是比较大头，时间久了就很熟悉了。想起大三上算法课的时候居然还和老师说快排是基于二分的思想。。。真是丢死人了
#include<stdio.h>
void quick_sort(int *a,int l,int h)
{
if(l<h)//如果分组里还有两个以上的元素，继续排序
{
int pivot=a[l];
int low=l;
int high=h;
while(low<high)
{
while(low<high&&a[high]>=pivot)
{
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=pivot)
{
low++;
}
a[high]=a[low];
}
a[low]=pivot;
quick_sort(a,l,low-1);
quick_sort(a,low+1,h);
}
else return ;
}
int main()
{
int a[10001];
int n,i;
while(scanf("%d",&n)!=EOF)
{
int len=n;
i=0;
while(n--)
{
scanf("%d",&a[i]);
i++;
}
quick_sort(a,0,len-1);
for(i=0;i<len;i++)
{
printf("%d ",a[i]);
}
}
return 0;
}