关于快排还有很多实现，比方说划分的时候元素的选取可以从两边进行，快排是原地重排。首先选取标准值（下面一个例子中选择中间位置那个元素），左边扫描大于该标准值的元素，右边扫描小于该标准值的元素。将扫描的元素交换位置即可，知道两个扫描指针位置相遇。快排是基于标准值的进行分类，所以我们很容易根据快排思想得到一个线性时间得到第k大元素的算法。基本思想就是首先找一个标准值分类，若是得到的左边值个数为k个则该值就是了，如若不然，若是个数小于k，则在右边继续扫描，若是大于k，则在左边扫描，直到得到的左值的个数为k个为止。利用该值可以得到前k个元素的值（无序）。
/*
取第k个元素k=0..n-1
参考网上吉林大学ACM模板
*/
#include<cstdio>
#include<cstdlib>
#define _cp(a,b)((a)<(b))
int kth_elem(int n,int *a,int k)
{
int t,key;
int l=0,r=n-1,i,j;
while(l<r){
for(key=a[((i=l-1)+(j=r+1))>>1];i<j;){
for(j--;_cp(key,a[j]);j--);
for(i++;_cp(a[i],key);i++);
if(i<j)t=a[i],a[i]=a[j],a[j]=t;
}
if(k>j)l=j+1;
else r=j;
}
return a[k];
}
int main()
{
int A[]={3,5,6,2,9,1};
printf("%d\n",kth_elem(6,A,3));
system("pause");
}