快排思想求第k个小数（java）

介绍

今天呢，介绍下使用快排的思想求第k个小的数。

• 首先选中一个数字将数组中比此数字小的数字放在左边大的数字放在右边，并返回这个数字是数组中的第几位。
• 如果选中数字的位数比我们k大，则在此数字左边的序列中寻找k,否则在右边寻找，直到找到那个数字。
• 如果不存在返回-1

程序代码

/***
	 * 求第k个小的数
	 * @param arr
	 * @param st
	 * @param end
	 * @param k
	 * @return
	 */
	public int findk(int arr[],int st,int end,int k){
		if(k<0||st+k-1>end)
			return -1;//不存在第K小数  
	    if(st==end)
	    	return st;//只有一个元素  
	    int q = partition(arr,st,end);//这是枢轴的下标，我们需要知道它在[st..end]中是第几个   
	    int i = q-st+1;//枢轴是第i小数  
	    if(i==k)return i;//找到  
	    else if(i>k)return findk(arr,st,q-1,k);//如果第K小数小于第i小数，则应该在枢轴的左边继续找  
	    else return findk(arr,q+1,end,k-i);
	}
	/***
	 * 
	 * @param a
	 * @param p
	 * @param r
	 * @return
	 */
	 public int partition(int a[],int p,int r){
		 int x=a[r];
		 int tmp;
		 int middle=p;
		 for(int j=p;j