Java使用二分法进行查找和排序的示例
实现二分法查找
二分法查找,需要数组内是一个有序的序列
二分查找比线性查找:数组的元素数越多,效率提高的越明显
二分查找的效率表示:O(log2N)N在2的M次幂范围,那查找的次数最大就是M, log2N表示2的M次幂等于N,省略常数,简写成O(logN)
如有一个200个元素的有序数组,那么二分查找的最大次数:
2^7=128,2^8=256,可以看出7次幂达不到200,8次幂包括,所以最大查找次数就等于8
//循环,二分查找 staticintbinarySearch(int[]array,intdata){ intstart=0; intend=array.length-1; intmid=-1; while(start<=end){ System.out.println("查找次数"); mid=(start+end)>>>1; if(array[mid]<data){ start=mid+1; }elseif(array[mid]>data){ end=mid-1; }else{ returnmid; } System.out.println("start="+start+",end="+end+",mid="+mid); } return-1; }
//递归二分查找初始start=0,end=array.length-1 staticintbinarySearch4Recursion(int[]array,intdata,intstart,intend){ intmid=-1; System.out.println("查找次数"); if(start>end){ returnmid; } mid=(start+end)>>>1; if(array[mid]<data){ returnbinarySearch4Recursion(array,data,mid+1,end); }elseif(array[mid]>data){ returnbinarySearch4Recursion(array,data,start,mid-1); }else{ returnmid; } }
二分法插入排序
设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
效率:O(N^2),对于初始基本有序的序列,效率上不如直接插入排序;对于随机无序的序列,效率比直接插入排序要高
/* *二分(折半)插入排序 *设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置 */ publicclassBinaryInsertSort{ publicstaticvoidmain(String[]args){ intlen=10; int[]ary=newint[len]; Randomrandom=newRandom(); for(intj=0;j<len;j++){ ary[j]=random.nextInt(1000); } binaryInsert(ary); /* *复杂度分析:最佳情况,即都已经排好序,则无需右移,此时时间复杂度为:O(nlgn)最差情况,全部逆序,此时复杂度为O(n^2) *无法将最差情况的复杂度提升到O(n|logn)。 */ //打印数组 printArray(ary); } /** *插入排序 *@paramary */ privatestaticvoidbinaryInsert(int[]ary){ intsetValueCount=0; //从数组第二个元素开始排序,因为第一个元素本身肯定是已经排好序的 for(intj=1;j<ary.length;j++){//复杂度n //保存当前值 intkey=ary[j]; //∆利用二分查找定位插入位置 //intindex=binarySearchAsc(ary,ary[j],0,j-1);//复杂度:O(logn) //intindex=binarySearchDesc(ary,ary[j],0,j-1);//复杂度:O(logn) intindex=binarySearchDesc2(ary,ary[j],0,j-1);//复杂度:O(logn) printArray(ary); System.out.println("第"+j+"个索引上的元素要插入的位置是:"+index); //将目标插入位置,同时右移目标位置右边的元素 for(inti=j;i>index;i--){//复杂度,最差情况:(n-1)+(n-2)+...+n/2=O(n^2) ary[i]=ary[i-1];//i-1<==>index setValueCount++; } ary[index]=key; setValueCount++; } System.out.println("\n设值次数(setValueCount)=====>"+setValueCount); } /** *二分查找升序递归 * *@paramary *给定已排序的待查数组 *@paramtarget *查找目标 *@paramfrom *当前查找的范围起点 *@paramto *当前查找的返回终点 *@return返回目标在数组中,按顺序应在的位置 */ privatestaticintbinarySearchAsc(int[]ary,inttarget,intfrom,intto){ intrange=to-from; //如果范围大于0,即存在两个以上的元素,则继续拆分 if(range>0){ //选定中间位 intmid=(to+from)/2; //如果临界位不满足,则继续二分查找 if(ary[mid]>target){ /* *mid>target,升序规则,target较小,应交换位置前置,即target定位在mid位置上, *根据查找思想,从from到mid-1认为有序,所以to=mid-1 */ returnbinarySearchAsc(ary,target,from,mid-1); }else{ /* *mid<target,升序规则,target较大,不交换位置,查找比较的起始位置应为mid+1 */ returnbinarySearchAsc(ary,target,mid+1,to); } }else{ if(ary[from]>target){//如5,4,要插入的是4 returnfrom; }else{ returnfrom+1; } } } /** *二分查找降序,递归 */ privatestaticintbinarySearchDesc(int[]ary,inttarget,intfrom,intto){ intrange=to-from; if(range>0){ intmid=(from+to)>>>1; if(ary[mid]>target){ returnbinarySearchDesc(ary,target,mid+1,to); }else{ returnbinarySearchDesc(ary,target,from,mid-1); } }else{ if(ary[from]>target){//如5,4,要插入的是4 returnfrom+1; }else{ returnfrom; } } } /** *二分查找降序,非递归 */ privatestaticintbinarySearchDesc2(int[]ary,inttarget,intfrom,intto){ //while(from<to){ for(;from<to;){ intmid=(from+to)>>>1; if(ary[mid]>target){ from=mid+1; }else{ to=mid-1; } } //from<==>to; if(ary[from]>target){//如5,4,要插入的是4 returnfrom+1; }else{ returnfrom; } } privatestaticvoidprintArray(int[]ary){ for(inti:ary){ System.out.print(i+""); } } }
打印
918562442531210216931706333132第1个索引上的元素要插入的位置是:1 918562442531210216931706333132第2个索引上的元素要插入的位置是:2 918562442531210216931706333132第3个索引上的元素要插入的位置是:2 918562531442210216931706333132第4个索引上的元素要插入的位置是:4 918562531442210216931706333132第5个索引上的元素要插入的位置是:4 918562531442216210931706333132第6个索引上的元素要插入的位置是:0 931918562531442216210706333132第7个索引上的元素要插入的位置是:2 931918706562531442216210333132第8个索引上的元素要插入的位置是:6 931918706562531442333216210132第9个索引上的元素要插入的位置是:9
设值次数(setValueCount)=====>24
931918706562531442333216210132