虽然C++有了现成的sort函数，但是快排的算法思想还是需要学习一下的。快速排序_百度百科

首先先找到一个分界值aim，通常用第一个数来充当。然后先从后往前寻找，比aim小的数，和aim交换，再从前往后找比aim大的数，和aim交换。重复这个步骤直到前者与后者相遇即停止，此时，数组已经被aim这个数分成两半，前面都比aim小，后面都比aim大，这时只需要递归求解其余部分即可

举个例子

49  38  65  97  76  13  27  49

i = 2   j = 8   aim = 49

第一趟 比aim小的数为27(j = 7)  比aim大的数为就 65(i=2) 交换后的序列为

27  38  49  97  76  13  65  49

第二趟 比aim小的数为13(j = 6)  比aim大的数为就 79(i=4) 交换后的序列为

27  38  13  49  76  97  65  49 

到这里第一次的交换就已经结束了。可以看到，49把所有的数，分成了两块，左边都比自己小

右边都比自己大。两边再分别调用函数，进行递归即可。

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。 

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。 

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。 

可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。

从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n)。 

 

void qsort(int l,int r) {if(l>=r)return ;int i=l+1;int j=r;int k=a[l];while(1) {while(i<=r&&a[i]<k)i++;while(j>=l&&a[j]>k)j--;if(i<j) {int t;t=a[i];a[i]=a[j];a[j]=t;} else break;}a[l]=a[j];a[j]=k;qsort(l,j-1);qsort(j+1,r);
}