java 中冒泡、二分、快速算法详解
1、冒泡算法的原理:
冒泡排序算法的一般性策略:搜索整个值列,比较相邻元素,如果两者的相对次序不对,则交换它们,其结果是最大值“想水泡一样”移动到值列的最后一个位置上,这也是它在最终完成排序的值列中合适的位置。然后再次搜索值列,将第二大的值移动至倒数第二个位置上,重复该过程,直至将所有元素移动到正确的位置上。
下面是两个Java冒泡算法程序
2、冒泡代码如下:
publicclassBubbleSort{ publicstaticvoidbubbleSort(int[]a){ inttemp; for(inti=0;ii;--j){ if(a[j] 2、二分算法
(1)前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
(2)原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法
(3)实现:代码如下
packageorg.cyxl.algorithm.search; /** *二分查找 *@authorcyxl * */ publicclassBinarySearch{ privateintrCount=0; privateintlCount=0; /** *获取递归的次数 *@return */ publicintgetrCount(){ returnrCount; } /** *获取循环的次数 *@return */ publicintgetlCount(){ returnlCount; } /** *执行递归二分查找,返回第一次出现该值的位置 *@paramsortedData已排序的数组 *@paramstart开始位置 *@paramend结束位置 *@paramfindValue需要找的值 *@return值在数组中的位置,从0开始。找不到返回-1 */ publicintsearchRecursive(int[]sortedData,intstart,intend,intfindValue) { rCount++; if(start<=end) { //中间位置 intmiddle=(start+end)>>1;//相当于(start+end)/2 //中值 intmiddleValue=sortedData[middle]; if(findValue==middleValue) { //等于中值直接返回 returnmiddle; } elseif(findValue>1;//相当于(start+end)/2 //中值 intmiddleValue=sortedData[middle]; if(findValue==middleValue) { //等于中值直接返回 returnmiddle; } elseif(findValue 4、测试代码
packageorg.cyxl.algorithm.search.test; importorg.cyxl.algorithm.search.BinarySearch; importorg.junit.Test; publicclassBinarySearchTest{ @Test publicvoidtestSearch() { BinarySearchbs=newBinarySearch(); int[]sortedData={1,2,3,4,5,6,6,7,8,8,9,10}; intfindValue=9; intlength=sortedData.length; intpos=bs.searchRecursive(sortedData,0,length-1,findValue); System.out.println("Recursice:"+findValue+"foundinpos"+pos+";count:"+bs.getrCount()); intpos2=bs.searchLoop(sortedData,findValue); System.out.println("Loop:"+findValue+"foundinpos"+pos+";count:"+bs.getlCount()); } }5、总结:这种查找方式的使用场合为已排序的数组。可以发现递归和循环的次数是一样的
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!