2012/4/4----随机选择法 博客分类： 算法

写算法之前先吐槽一下，今天实在是不适合骑车。昨晚花了一个小时洗车，准备干粮，各种骑行装备全都检查一遍就为今天的骑行。早上6点起床，7点准时集合出发，但是出发后就开始下雨。结果我们冒雨骑了近40km，不仅全身湿透（没有挡泥板的车，雨天真的不想再骑了），还满背是泥。并且由于雨越下越大，路又滑导致骑行速度提不上去，全程140km已经不能顺利完成了，只有半途返回。

但是悲剧的事情又发生了，在返回的途中一朋友的车胎爆了，大家又在雨中花了近1个小时补胎（主要是车胎不好补，一次性爆了两个大洞，无奈）。回来之后照镜子看了一下，全身是泥，昨晚刚洗的车已经看不出车样了，于是又花了20分钟洗车。。。

好了，吐槽结束，开始写算法了。

随机选择法（RANDOMIZED-SELECT）：选择出数组A经过排序后的第i个数（有一个专业名词需要了解--顺序统计量），常规方式是先对数组A进行排序，然后再取出A[i]的值就可以了。但是，使用先排序再选取这种方式，它的时间效率不太好。所以，这里我们使用“随机选择法”。其核心思想有点像快速排序，先找一个关键字key查看其所在数组中的位置q，然后再比较q和i的大小，如果i=q，则我们直接就可以取出关键字key；如果i>q,则我们又在[q+1...]这个范围内选择关键字进行比较，直到找到i=q为止；如果i<d,我们就在[0...q-1]这个范围内继续选择关键字进行比较，直到找到i=q为止。

至于详细的思想，程序中有足够的注释帮助理解。

/*
 * 随机选择法求数组中的”顺序统计量“----即在排序后的数组中，A[i]的值
 * @version 1.0 2012/4/4
 * @author akon
 */
package com.akon405.www;

public class RandomizedSelect {
	//randomized_Select函数可以求得A排序过后的A[i]的值
	public int randomized_Select(int[] A,int left,int right,int i){
		if(left==right){//如果数组只有一个元素的情况下直接返回数组中唯一的元素
			return A[left];
		}
		int q=division(A,left,right);//q为分割点的下标(数组A以key值为界限，分为两拨。key前面的数值比key小，key后面的数值比key大)
		if(i==q){//i等于分割点的下标
			return A[q];
		}else if(i<q){//i小于分割点的下标，则可以确定i在[left,q-1]这个区间里
			return randomized_Select(A,left,q-1,i);
		}else{//i大于分割点的下标，则可以确定i在[q+1,right]这个区间里
			return randomized_Select(A,q+1,right,i);
		}
		
	}
	
	//division函数可以实现对A的分割，把A按照关键字key进行分割，一部分比key大，一部分比key小（这里的key选定为数组A的第一个数据），最后返回分割点的下标
	public int division(int[] A,int left,int right){
		int key=A[left];//确定最右边的数组元素为关建数值
		int temp;
		//下面循环可以把输入的数组A以key值为界限，分为两拨。key前面的数值比key小，key后面的数值比key大
		while(left!=right){
		while(left<right&&key<A[right])
			right--;//从右向左找出比key小的第一个数值，下标为right
		temp=A[right];
		A[right]=A[left];
		A[left]=temp;
		while(left<right&&key>A[left])
			left++;//从左向右找出比key大的第一个数值，下标为left
		temp=A[right];
		A[right]=A[left];
		A[left]=temp;
		}
		return left;//分割点的下标，left=right
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={20,19,3,1,87,32,65};
		RandomizedSelect rs=new RandomizedSelect();
		int right=A.length-1;//数组的右边
		int left=0;//数组的左边
		int i=6;//第i个”顺序统计量“--即在排序后的数组中，A[i]的值
		if(i<=right)
		System.out.print(rs.randomized_Select(A, left, right, i));//输出这个所求的数据
	}

}