2012 / 4 / 4 - --- 랜 덤 선택 법

알고리즘 을 쓰기 전에 먼저 토로 해 보 세 요. 오늘 은 정말 자전 거 를 타기 에 적합 하지 않 습 니 다.어젯밤 에 한 시간 동안 세 차 를 하고 식량 을 준 비 했 습 니 다. 각종 자전거 장 비 를 모두 검사 해서 오늘 의 자전 거 를 위해 서 였 습 니 다.아침 6 시 에 일어나 7 시 정각에 모여 출발 했 지만 출발 하 자마자 비가 내리 기 시작 했다.결국 우 리 는 비 를 맞 으 며 40km 가까이 탔 다. 온몸 이 흠뻑 젖 었 을 뿐만 아니 라, 비 오 는 날 에는 정말 더 이상 타고 싶 지 않 았 다.또한 비가 많이 내 릴 수록 길이 미 끄 러 워 서 자전 거 를 타 는 속도 가 올 라 가지 못 해 전체 140 km 가 순조롭게 완성 되 지 못 하고 도중에 돌아 올 수 밖 에 없 었 다.
그러나 비 극적인 일이 또 발생 했다. 돌아 오 는 길에 한 친구 의 타이어 가 터 졌 고 모두 빗속 에서 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));//         
	}

}