算法起步之选择算法

          什么是选择算法，其实很简单，从一堆数里选择最大值或最小值就是选择算法。这样一说大家是不是觉得太简单了，其实选择算法，选择并不只是选择最大或是最小，相信这样的算法大家都能写的出来，一趟遍历就可以得到，但是选择算法是找出第几小或者是第几大的数，这样是不是没有刚才说的那么简单了呢。但是他们期望的时间复杂度却都是相同的都是O（n），简单的说就是希望一趟遍历就可以得到第几小第几大的数，其实选择算法跟上一篇我们说的额快排在实现上是有很多相似的地方的。

public class Select {
	public int randomselect(int[] map,int start,int end,int loc){
		int p=getPlocation(map, start, end);
		if(p>loc){
			return randomselect(map, start, p-1, loc); 
		}
		if(p<loc){
			return randomselect(map, p+1, end, loc);
		}
		return map[p];
	}
	public int getPlocation(int[] map,int start,int end){
		int core=map[end];
		int i=start-1;
		for (int j = start; j <=end-1; j++) {
			if (map[j]<core) {
				i++;
				int cache=map[j];
				map[j]=map[i];
				map[i]=cache;
			}
		}
		i++;
		map[end]=map[i];
		map[i]=core;
		return i;
	}
	
	public int start(int[] map,int size,int target){
		return randomselect(map, 0, size-1, target-1);
	}
	
	public static void main(String[] args) {
		int[] map=new int[]{4,1,5,3,7,12,65,7};
		
		Select s=new Select();
		int result=s.start(map, map.length, 8);
		System.out.println(result);
	}

}

算法起步之选择算法

原文：http://www.cnblogs.com/lonelyxmas/p/3562013.html