K分位数问题

K分位数问题实现，对一个含有n个元素的集合来说，所谓的k分位数，就是能把已排序的集合分成k个大小相等的集合的“k-1个顺序统计量”。请给出一个能求出含有n个元素（无序）的集合的k分位数的O(nlgk)时间的算法。

以下为程序代码：

	public static void findKthQuantile(int[] src, int p, int r, int k){
		if (k==1)return;
		int med = ArrayOrder.randomSelect(src, p, r, ((r-p+1)/k)*(k/2));
		System.out.println(med);
		partition(src, med);
		findKthQuantile(src, p, p+((r-p+1)/k)*(k/2)-1, k/2);
		findKthQuantile(src, p+((r-p+1)/k)*(k/2), r, k-k/2);
	}
	
	public static void partition(int[] src, int m){
		int j = 0;
		int temp;
		for (int i = 0; i < src.length; i++) {
			if (src[i]<=m) {
				temp = src[i];
				src[i] = src[j];
				src[j++] = temp;
			}
		}
	}

 public static int randomSelect(int[] src, int p, int r, int i) {
    	if (p == r) return src[p];

    	int q = partitionRandom(src, p, r);
    	//int q = partition(src, p, r);
    	if ((q-p+1)==i) {
			return src[q];
		}
    	else if ((q-p+1)>i) {
			return randomSelect(src, p, q-1, i);
		}else {
			return randomSelect(src, q+1, r, i-q+p-1);
		}
	}

 public static int partitionRandom(int[]src, int p, int r){
    	int i = new Random().nextInt(r-p) + p;
    	int temp = src[r];
    	src[r] = src[i];
    	src[i] = temp;
    	return partition(src, p, r);
 }