本文主要是介绍递归与分治策略-2.9.1线性时间选择(随机划分基准)(第k小问题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
import java.util.Random;
/*** 线性时间选择——随机选择*/
public class test2_9_1 {static Comparable a[] = {"49","38","65","97","76","13","27"};/*** 返回(left~right)内第k小元素*/private static Comparable randomizedSelect(int left,int right,int k){if(left == right) return a[left];int i = randomizedPartition(left,right);int j = i-left+1; //[left,i]区间的元素个数/*** 此处不能是if(k<j) return randomizedSelect(left,i+1,k);* 理论上这样写是对的，但是如果随机基准划分到数组尾元素就会下标越界,因为i∈[left,right]!!!* 故在k>j条件下说明i<right,则[i+1,right]一定不会越界* 而在k<j条件下说明存在i=right的可能性,则[left,i+1]会越界！！*/if(k<=j) return randomizedSelect(left,i,k); //切记是i不是j,因为j表示基准i之前元素的个数,是相对的值,而i是绝对的下标else return randomizedSelect(i+1,right,k-j);}/*** 利用随机快排思想，求得划分基准的下标*/private static int randomizedPartition(int left,int right){Comparable temp;//1.取一个(left~right)的随机整数Random random = new Random();int i = random.nextInt(right-left)+left; //2.交换首元素和随机数下标对应数组元素的值temp = a[i];a[i] = a[left];a[left] = temp;//3.返回划分元素的位置并将比其大的排右，比其小的排左return partition(left,right);}private static int partition(int left,int right){int i = left,j = right+1;Comparable x = a[left],temp;while(true){while(a[++i].compareTo(x)<0&&i<right);while(a[--j].compareTo(x)>0);if(i>=j){a[left] = a[j];a[j] = x;break;}temp = a[i];a[i] = a[j];a[j] = temp;}return j;}public static void main(String[] args) {int k = 5;System.out.print("初始元素:");for(int i=0;i<a.length;i++)System.out.print(a[i]+" ");System.out.println();System.out.println("第"+k+"小元素:"+randomizedSelect(0,a.length-1,k));}
}
运行结果如下：
初始元素:49 38 65 97 76 13 27
第5小元素:65重点代码是第20和21行代码，笔者已经在注释中写清参数符号唯一性的原由！
这篇关于递归与分治策略-2.9.1线性时间选择(随机划分基准)(第k小问题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
