duyifei0 2019-06-26
大概半个月前,偶尔看到《算法图解》,没翻几页便被数学战五渣的我奉为神书,怎一个相见恨晚、爱不释手加老泪纵横啊!遂写文以作积累……
选择排序的思路很好理解,以从小到大排序为例:
示例将对int[]
进行排序,为了方便处理 int[] 数组 中的索引信息,构建了PositionBean
类。(后续的探讨其它算法的文章中,也多以int[]为例,同样会用到PositionBean)
public class PositionBean { int val; //值 int index; //索引 public PositionBean(int val, int index) { this.val = val; this.index = index; } //省略setter和getter方法…… }
算法实现
private static PositionBean findMin(int source[]){ int minIndex = 0; int min=source[minIndex]; //最小值min,初始化为第一个元素 for(int i=1,len=source.length;i<len;i++){ //轮询source[],找到比当前min小的元素,给min重新赋值,并记录最小值索引minIndex if(min>source[i]){ min=source[i]; minIndex = i; } } return new PositionBean(min,minIndex); }
public static int[] doOrder(int source[]){ if(source==null || source.length==0){ return source; } int len=source.length; int res[] = new int[len]; for(int i=0;i<len;i++){ PositionBean bean = findMin(source); res[i] = bean.getVal(); source = removeElement(source,bean.getIndex()); //移除元素 } return res; }
/** * 移除source[]中,索引为index的元素 * @param source * @param index * @return */ private static int[] removeElement(int source[],int index){ int len = source.length; int res[] = new int[len-1]; int resIndex =0; for(int i=0;i<len;i++){ if(index==i){ continue; } res[resIndex] = source[i]; resIndex++; } return res; }
代码很简单,不多做解释。
大家以前玩没玩过猜数游戏?一个人(张三)先写下1到100的数字中任意一个数,另一个人(李四)去猜,张三根据对方的猜测情况提示“大了”、“小了”,直到猜对!
李四可以选择从1开始猜,接下来的剧情会是这样的:
李:1 张:小了 李:2 张:小 ……
这种猜法,最多猜100次。也就是说,最坏情况做了集合遍历,时间复杂度记作O(n)
当然李四也有另外的选择:
李:50 张:小了 李:25 张:大了 ……
小李子每次都选择了中间的数字进行猜,而通过张三的提示,每次都能排除当前集合近半的不符合条件的数字:将当前集合(1~100)以 中间数字 进行分隔,要么在数字较小的结合中(1~50),要么在数字较大的集合中(51~100)。
这种方式,就是我们要探讨的二分查找,也叫折半查找。给出示意图:
第一次比较后,由于目标值大于中间数(target=10 > 中间数=8),因此中间数左侧(含中间数)数字-1,1,5,8
已然出局(图中第二次比较,将出局的数字格画成了虚线)
依照上面的示意图写出代码:
/** * 在source[]中寻找target,如果找不到抛出异常RuntimeException(target+"不存在") * @param target * @param source * @return */ public static int doFind(int target,int source[]){ if(source==null || source.length==0){ throw new RuntimeException("集合为空"); } int low = 0; int height = source.length-1; do{ int halfIndex = (low+height)/2; //中间索引 int halfVal = source[halfIndex]; //中间索引对应的数字 if(target==halfVal){ //发现目标 return halfIndex; }else if(target>halfVal){ //如果target大于中间的数字,更新低位索引=中间索引+1 low=halfIndex+1; }else{ height=halfIndex-1; } }while (low<=height); throw new RuntimeException(target+"不存在"); }
二分查找与线性查找相比,时效方面有着明显的优势。
二分查找每次都将查找数据集缩小1/2,那问个问题——在n个数中查找,利用折半算法每次都能将数据集减半(除2),多少次能得到结果(将数据集缩小到2以内)?这个问题再抽象一下:整数n除以多少次数字2,能得到1或0?再换一种问法问:多少个2相乘,能够大于等于(正)整数n?
如果没有把高中数学知识还给物理老师的话,你应该多多少少闻到了些对数的味道!
Tips: 你可能不记得对数了,但很可能记得什么是幂。"2³=?"就是一个幂运算,显然2³=8。 那么多少个2相乘是8?这就是对数运算,可以简单记作"log8=?"。对数运算是幂运算的逆运算。
如果还想加深有关对数的理解,可以看下这篇文章——如何理解对数?
说了这么多,其实是在推导这个结论:二分查找的时间复杂度是O(log n)
。
二分法快则快矣,但是有个很大的限制,只能用于有序集合的查找。如果本身是一个无序的集合,只能先排序再强行二分。
还有就是,java已经为我们实现了二分查找,详见Collections.binarySearch
。