原文:
什么是选择算法,其实很简单,从一堆数里选择最大值或最小值就是选择算法。这样一说大家是不是觉得太简单了,其实选择算法,选择并不只是选择最大或是最小,相信这样的算法大家都能写的出来,一趟遍历就可以得到,但是选择算法是找出第几小或者是第几大的数,这样是不是没有刚才说的那么简单了呢。但是他们期望的时间复杂度却都是相同的都是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看了代码,会发现其实跟快排是很相似的,基本就是完全一样,只是选择算法只处理一侧,而快排是两侧都处理。 友情提示:转载请注明出处 【作者:idlear 博客: idlear 】
posted on 2014-02-23 15:41 阅读( ...) 评论( ...)