第九届蓝桥杯大赛个人赛省赛（软件类）Java类 真题 第五题 标题：快速排序

package com.wzxy.test;

import java.util.Random;

public class Main2{
	
	public static void main(String args[]) {	//0 1 2 3 4 5
		int [] a = {1, 4, 2, 8, 5, 7};			//1 2 4 5 7 8 
		System.out.println(quickSelect(a, 0, 5, 4));	//a为数组 ，0-5为数组下标范围，4为k表示第k小的
	}
	public static int quickSelect(int a[], int l, int r, int k) {
		Random rand = new Random();
		int p = rand.nextInt(r - l + 1) + l;
		int x = a[p];
		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
		int i = l, j = r;
		while(i < j) {
                	while(i < j && a[i] < x) i++;
                	if(i < j) {
                        	a[j] = a[i];
                        	j--;
                	}
                	while(i < j && a[j] > x) j--;
                	if(i < j) {
                        	a[i] = a[j];
                        	i++;
                	}
        	}
        	a[i] = x;
        	p = i;
        	if(i - l + 1 == k) return a[i];
        	if(i - l + 1 < k) return quickSelect( _______________ ); //填空
        	else return quickSelect(a, l, i - 1, k);	
	}
}