[cpp]
#include <stdio.h>
#include <stdlib.h>

void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}

//对arr数组做从下标0到下标q的划分
int partition(int *arr,int p,int q)
{
int low = p+1,high = q;
int x = arr[p];

while(low<high)
{
if(arr[low]<=x)
low++;
else
{
swap(&arr[low],&arr[--high]);
}
}
swap(&arr[p],&arr[--low]);

return low;

}

int rand_partition(int *arr,int p,int q)
{
int rnd = p + rand()%(q-p);
swap(&arr[p],&arr[rnd]);
return partition(arr,p,q);
}

int getK(int *arr,int p,int q,int k)
{
if(p==q)
{
return arr[p];
}
int pos = partition(arr,p,q);
int j = pos-p+1;

if(k<=j)
{
return getK(arr,p,pos,k);
}
else
{
return getK(arr,pos+1,q,k-j);
}

}

int main()
{
int arr[6] = {1,2,3,4,5,6};

printf("%d\n",getK(arr,0,5,5));
/*
partition(arr,0,5);
for(int i=0;i<6;i++)
{
printf("%d ",arr[i]);
}
*/

return 0;
}

[/cpp]