Java常用基本算法

4.1算法前面我们已经讲过，程序=数据结构+算法。什么是算法？对一个现有的问题我们采取的解决过程及方法，即为算法。一个用算法实现的程序会耗费两种资源：处理时间和内存。算法的效率分析标准：时间复杂度空间复杂度简单性和清晰性对于时间复杂度，可以通过System.currentTimeMillis()方法来测试。例如：publicclassTest{publicstaticvoidmain(Stringargs[]){System.out.println(System.currentTimeMillis());fun();System.out.println(System.currentTimeMillis());}publicstaticvoidfun(){doublea=0;for(inti=0;i10000;i++)for(intj=0;j10000;j++)for(intk=0;k100;k++)a++;}}前后两次获得当前系统时间的差值就是运行所消耗的时间（毫秒为单位）。通过System.currentTimeMillis()方法来测试的缺点：a.不同的平台执行的时间不同b.有些算法随着输入数据的加大，测试时间会变得不切实际！4.2查找4.2.1查找之线性查找（直接查找）算法思路：从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。注意：被查找的数组中的元素可以是无序的、随机的。实例：importjava.util.*;publicclassDemo1{publicstaticvoidmain(Stringargs[]){intiArr[]={32,9,78,44,29,18,97,49,56,61};System.out.println(数组的所有元素为：);for(inti:iArr)System.out.print(i+);System.out.println();System.out.print(请输入你要查找的元素：);Scannerscan=newScanner(System.in);intiNum=scan.nextInt();intindex=straightSearch(iArr,iNum);if(index==-1)System.out.println(没有找到元素+iNum);elseSystem.out.println(找到元素+iNum+,下标为:+index);}publicstaticintstraightSearch(int[]arr,intnum){inti=0;for(;iarr.length;i++){if(arr[i]==num)returni;}return-1;}}4.2.2查找之折半查找（二分查找）算法思路：假设被查找数组中的元素是升序排列的，那我们查找值时，首先会直接到数组的中间位置(数组长度/2)，并将中间值和查找值比较，如果相等则返回，否则，如果当前元素值小于查找值，则继续在数组的后面一半查找(重复上面过程)；如果当前元素值大于查找值，则继续在数组的前面一半查找，直到找到目标值或者无法再二分数组时停止。注意：二分查找只是针对有序排列的各种数组或集合。实例：//不利用递归实现importjava.util.*;publicclassDemo1{publicstaticvoidmain(Stringargs[]){intiArr[]={1,2,3,4,6,8,22,44,99,111,112,116};System.out.println(数组的所有元素为：);for(inti:iArr)System.out.print(i+);System.out.println();System.out.print(请输入你要查找的元素：);Scannerscan=newScanner(System.in);intiNum=scan.nextInt();intindex=binarySearch(iArr,iNum,0,iArr.length-1);if(index==-1)System.out.println(没有找到元素+iNum);elseSystem.out.println(找到元素+iNum+,下标为:+index);}publicstaticintbinarySearch(int[]arr,intnum,intiMin,intiMax){while(iMin=iMax){intiMid=(iMin+iMax)/2;if(num==arr[iMid])returniMid;elseif(numarr[iMid])iMax=iMid-1;elseiMin=iMid+1;}return-1;}}//利用递归实现importjava.util.*;publicclassDemo1{publicstaticvoidmain(Stringargs[]){intiArr[]={1,2,3,4,6,8,22,44,99,111,112,116};System.out.println(数组的所有元素为：);for(inti:iArr)System.out.print(i+);System.out.println();System.out.print(请输入你要查找的元素：);Scannerscan=newScanner(System.in);intiNum=scan.nextInt();intindex=binarySearch(iArr,iNum,0,iArr.length-1);if(index==-1)System.out.println(没有找到元素+iNum);elseSystem.out.println(找到元素+iNum+,下标为:+index);}publicstaticintbinarySearch(int[]arr,intnum,intiMin,intiMax){intiMid=(iMin+iMax)/2;if(numarr[iMin]||numarr[iMax])return-1;elseif(num==arr[iMid])returniMid;elseif(numarr[iMid])returnbinarySearch(arr,num,iMin,iMid-1);elsereturnbinarySearch(arr,num,iMid+1,iMax);}}4.3排序4.3.1排序之插入排序4.3.1.1插入排序之直接插入排序算法思路：直接插入排序(straightinsertionsort)是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中，使之仍保持有序，从而得到一个新的长度为m+1的有序表。设有一组关键字｛K1，K2，…，Kn｝；排序开始就认为K1是一个有序序列；让K2插入上述表长为1的有序序列，使之成为一个表长为2的有序序列；然后让K3插入上述表长为2的有序序列，使之成为一个表长为3的有序序列；依次类推，最后让Kn插入上述表长为n-1的有序序列，得一个表长为n的有序序列。实例：//49,38,65,97,76,13,27初始情况//[49],38,65,97,76,13,27从下标1开始//[38,49],65,97,76,13,27//[38,49,65],97,76,13,27//[38,49,65,97],76,13,27//[38,49,65,76,97],13,27//[13,38,49,65,76,97],27//[13,27,38,49,65,76,97]代码实现：publicclassTest{publicstaticvoidmain(String[]args){inta[]={49,38,65,97,76,13,27};straightInsertSort(a);for(inti=0;ia.length;i++)System.out.print(a[i]+);System.out.println();}publicstaticvoidstraightInsertSort(inta[]){inti,m;for(i=1;ia.length;i++)//共进行n-1趟插入{m=i;while(m=1&&a[m]a[m-1])//短路表达式{a[m]=(a[m]+a[m-1])-(a[m-1]=a[m]);//比前一个小,则与之交换m--;}}}}4.3.1.2插入排序之折半插入排序算法思路：折半插入排序(Binaryinsertionsort)当直接插入排序进行到某一趟时，对于a[i]来讲，前边i-1个记录已经按有序。此时不用直接插入排序的方法，而改为先用折半查找法找出r[i]应插的位置，然后再插入。这种方法就是折半插入排序。基本步骤：a、初始化：设定有序区为第一个元素，设定无序区为后面所有元素b、依次取无序区的每个元素c、通过二分法查找有序区，返回比这个数小的最大数d、保留此位置数据e、从此位置的元素到有序区的最后一个元素，依次后移f、用保留的数据填充此位置代码实现：publicclassTest{publicstaticvoidmain(String[]args){inta[]={49,38,65,97,76,13,27};binaryInsertSort(a);for(inti=0;ia.length;i++)System.out.print(a[i]+);System.out.println();}publicstaticvoidbinaryInsertSort(inta[]){for(inti=1;ia.length;i++)//共进行n-1趟插入{intiTmp=a[i];//将待插入数据临时保存到iTmp中去.intm=findPosition(a,a[i],0,i-1);//m是a[i]应该呆的位置for(intj=i;jm;j--)a[j]=a[j-1];//整体向后移动一个位置a[m]=iTmp;//m是a[i]应该呆的位置}}publicstaticintfindPosition(inta[],intnum,intiMin,intiMax){if(numa[iMin])returniMin;//超出范围,直接返回if(numa[iMax])returniMax+1;//超出范围,直接返回intiMid=(iMin+iMax)/2;//选取中值,准备二分if(a[iMid]=num)//继续二分:递归returnfindPosition(a,num,iMin,iMid-1);//目标在左边,递归左边(p[m]已经比较过,排出查找范围)else//if(a[m]num)returnfindPosition(a,num,iMid+1,iMax);//目标在右边,递归右边(p[m]已经比较过,排出查找范围)}}4.3.1.3插入排序之希尔排序算法思路：希尔排序(ShellSort):是插入排序的一种。因D．L．Shell于1959年提出而得名。先取一个小于数组长度n的整数d1(一般为n/2)作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1(一般为d1/2),重复上述的分组和排序，直至所取的增量dt=1(dtdt-l…d2d1)，即所有记录放在同一组中进行直接插入排序为止。代码实现：publicclassTest{publicstaticvoidmain(String[]args){inta[]={49,38,65,97,76,13,27};shellSort(a);for(inti=0;ia.length;i++)System.out.print(a[i]+);System.out.println();}publicstaticvoidshellSort(inta[]){intk=a.length