Java面试——算法

算法1、二分查找算法1.1、二分查找算法的原理1.2、二分查找算法的Java实现2、冒泡排序算法2.1、冒泡排序算法的原理2.2、冒泡排序算法的Java实现3、插入排序算法3.1、插入排序算法的原理3.2、插入排序算法的Java实现4、快速排序算法4.1、快速排序算法的原理4.2、快速排序算法的Java实现5、希尔排序算法5.1、希尔排序算法的原理5.2、希尔排序算法的Java实现6、归并排序算法6.1、归并排序算法的原理6.2、归并排序算法的Java实现7、桶排序算法7.1、桶排序算法的原理7.2、桶排序算法的Java实现8、基数排序算法8.1、基数排序算法的原理8.2、基数排序算法的Java实现9、其他算法9.1、剪枝算法9.2、回溯算法9.3、最短路径算法在计算机世界里“数据结构算法程序”​因此算法在程序开发中起着至关重要的作用。虽然我们在开发中自己设计算法的情况不多在工作中却离不开算法。无论是开发包提供的算法还是我们自己设计的算法算法在程序中都无处不在。常用的算法有查找算法和排序算法。查找算法有线性查找算法、深度优先搜索算法、广度优先搜索算法和二分查找算法这里重点介绍最常用也最快速的二分查找算法。排序算法是很常见的算法大到数据库设计小到对列表的排序都适用。常用的排序算法有冒泡排序算法、插入排序算法、快速排序算法、希尔排序算法、归并排序算法、桶排序算法、堆排序算法和基数排序算法。除此之外还会介绍一些在应用中必不可少的算法例如剪枝算法、回溯算法、最短路径算法、最大子数组算法和最长公因子算法。1、二分查找算法二分查找算法又叫作折半查找要求待查找的序列有序每次查找都取中间位置的值与待查关键字进行比较如果中间位置的值比待查关键字大则在序列的左半部分继续执行该查找过程如果中间位置的值比待查关键字小则在序列的右半部分继续执行该查找过程直到查找到关键字为止否则在序列中没有待查关键字。1.1、二分查找算法的原理如图所示在有序数组[3,4,6,20,40,45,51,62,70,99,110]中查找key20的数据根据二分查找算法只需查找两次便能命中数据。这里需要强调的是二分查找算法要求要查找的集合是有序的如果不是有序的集合则先要通过排序算法排序后再进行查找。1.2、二分查找算法的Java实现二分查找算法的Java实现如下publicstaticintbinarySearch(int[]array,inta){intlow0;inthigharray.length-1;intmid;while(lowhigh){mid(lowhigh)/2;//中间位置if(array[mid]a){returnmid;}elseif(aarray[mid]){//向右查找lowmid1;}else{//向左查找highmid-1;}}return-1;}以上代码定义了方法binarySearch()用于二分查找在该方法中有3个变量low、mid和high分别表示二分查找的最小、中间和最大的数据索引。在以上代码中通过一个while循环在数组中查找传入的数据在该数据大于中间位置的数据时向右查找即最大索引位置不变将最小索引设置为上次循环的中间索引加1在该数据小于中间位置的数据时向左查找即最小索引位置不变然后将最大索引设置为上次循环的中间索引并减1。重复以上过程直到中间索引位置的数据等于要查找的数据说明找到了要查找的数据将该数据对应的索引返回。如果遍历到lowhigh还没有找到要查找的数据则说明该数据在列表中不存在返回-1。2、冒泡排序算法冒泡排序Bubble Sort算法是一种较简单的排序算法它在重复访问要排序的元素列时会依次比较相邻的两个元素如果左边的元素大于右边的元素就将二者交换位置如此重复直到没有相邻的元素需要交换位置这时该列表的元素排序完成。该算法名称的由来是越大的元素会经过交换慢慢“浮”到数列的顶端升序或降序排列​就如同水的气泡最终会上浮到顶端一样。2.1、冒泡排序算法的原理如图所示为对数组[4,5,6,3,2,1]进行冒泡排序每次都将当前数据和下一个数据进行比较如果当前数据比下一个数据大就将二者交换位置否则不做任何处理。这样经过第1趟排序就会找出最大值6并将其放置在最后一位经过第2趟排序就会找出次大的数据5放在倒数第二位如此重复直到所有数据都排序完成。2.2、冒泡排序算法的Java实现冒泡排序算法的Java实现如下publicstaticint[]bubbleSort(int[]arr){//外层循环控制排序趟数for(inti0;iarr.length-1;i){//内层循环控制每一趟排序多少次for(intj0;jarr.length-1-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}returnarr;}以上代码实现了一个名为bubbleSort()的冒泡排序算法分为外层循环和内层循环外层循环控制排序的次数内层循环控制每一趟排序多少次。在内层循环中比较当前数据和下一个数据的大小如果当前数据大于下一个数据就交换二者的位置这样重复进行判断直至整个排序完成最终返回排序后的数组。3、插入排序算法插入排序Insertion Sort算法是一种简单、直观且稳定的排序算法。如果要在一个已排好序的数据序列中插入一个数据但要求此数据序列在插入数据后仍然有序就要用到插入排序法。插入排序的基本思路是将一个数据插入已经排好序的序列中从而得到一个新的有序数据该算法适用于少量数据的排序是稳定的排序方法。3.1、插入排序算法的原理插入排序算法的原理如图5-3所示类似于扑克牌游戏的抓牌和整理过程。在开始摸牌时左手是空的。接着每次从桌上摸起一张牌时都根据牌的大小在左手扑克牌序列中从右向左依次比较在找到第一个比该扑克牌大的位置时就将该扑克牌插入该位置的左侧这样依次类推无论什么时候左手中的牌都是排好序的。如图所示为插入排序算法的工作流程。输入原始数组[6, 2, 5, 8, 7 ]​在排序时将该数组分成两个子集一个是有序的Lleft子集一个是无序的Rright子集。初始时设L[ 6 ], R [ 2, 5, 8, 7 ]​。在L里面只有一个元素4本身就是有序的。接着我们每次都从R中拿出一个元素插入L中从右到左比自己大的元素后面然后将L中比自己大的所有元素整体后移这样就保证了L子集仍然是有序的。重复以上插入操作直到R子集的数据为空这时整个数组排序完成排序的结果被保存在L子集中。3.2、插入排序算法的Java实现插入排序算法的Java实现如下publicstaticint[]insertSort(intarr[]){for(inti1;iarr.length;i){//插入的数intinsertValarr[i];//被插入的位置准备和前一个数进行比较intindexi-1;//如果插入的数比被插入的数小while(index0insertValarr[index]){//则将arr[index]向后移动arr[index1]arr[index];//将index向前移动index--;}//将插入的数放入合适的位置arr[index1]insertVal;}returnarr;}以上代码定义了insertSort()用于插入排序其中insertVal用于从数组中取出待插入的数据index是待插入的位置。在insertSort()中通过while循环从数组中找到比待插入数据大的数据的索引位置index然后将该index位置后的元素向后移动接着将待插入的数据插入index1的位置如此重复直到整个数组排序完成。4、快速排序算法快速排序Quick Sort是对冒泡排序的一种改进通过一趟排序将要排序的数据序列分成独立的两部分其中一部分的所有数据比另一部分的所有数据都要小然后按此方法对两部分数据分别进行快速排序整个排序过程递归进行最终使整个数据序列变成有序的数据序列。4.1、快速排序算法的原理快速排序算法的原理是选择一个关键值作为基准值一般选择第1个元素为基准元素​将比基准值大的都放在右边的序列中将比基准值小的都放在左边的序列中。具体的循环过程如下。从后向前比较用基准值和最后一个值进行比较。如果比基准值小则交换位置如果比基准值大则继续比较下一个值直到找到第1个比基准值小的值才交换位置。在从后向前找到第1个比基准值小的值并交换位置后从前向后开始比较。如果有比基准值大的则交换位置如果没有则继续比较下一个直到找到第1个比基准值大的值才交换位置。重复执行以上过程直到从前向后比较的索引大于等于从后向前比较的索引则结束一次循环。这时对于基准值来说左右两边都是有序的数据序列。重复循环以上过程分别比较左右两边的序列直到整个数据序列有序。如图所示是对数组[6,9,5,7,8]进行快速排序。先以第1个元素6为基准值从数组的最后一位从后向前比较比较顺序为86、76、56​找到第1个比6小的数据5然后进行第1次位置交换即将数据6索引为0和数据5索引为2交换位置之后基准值6位于索引2处接着从前向后比较比较顺序为56、96​找到第1个比6大的数据9然后进行第2次位置交换即将数据6索引为2和数据9索引为1交换位置交换后6位于索引1处这时高位和低位都在6处第一次递归完成。在第一次递归完成后基准值6前面的数据都比6小基准值6后面的数据都比6大。重复执行上述过程直到整个数组有序。4.2、快速排序算法的Java实现快速排序算法的Java实现如下publicstaticint[]quickSort(int[]arr,intlow,inthigh){intstartlow;//从前向后比较的索引intendhigh;//从后向前比较的索引intkeyarr[low];//基准值while(endstart){//从后向前比较while(endstartarr[end]key)end--;//如果没有比基准值小的则比较下一个直到有比基准值小的则交换位置然后又从前向后比较if(arr[end]key){inttemparr[end];arr[end]arr[start];arr[start]temp;}//从前向后比较while(endstartarr[start]key)start;//如果没有比基准值大的则比较下一个直到有比基准值大的则交换位置if(arr[start]key){inttemparr[start];arr[start]arr[end];arr[end]temp;}//此时第1次循环比较结束基准值的位置已经确定。左边的值都比关键值小//右边的值都比关键值大但是两边的顺序还有可能不一样接着进行下面的递归调用}//递归左边序列从第1个索引位置到“关键值索引-1”if(startlow)quickSort(arr,low,start-1);//递归右边序列从“关键值索引1”到最后一个位置if(endhigh)quickSort(arr,end1,high);returnarr;}以上代码定义了名为quickSort()的快速排序方法在该方法中定义了3个变量start、end和key分别表示从前向后比较的索引、从后向前比较的索引和基准值。具体过程为①通过while循环从后向前比较找到比基准值小的则交换位置②通过while循环从前向后比较找到比基准值大的则交换位置③根据从前向后比较的索引和从后向前比较的索引的大小不断递归调用直到递归完成返回排序后的结果。5、希尔排序算法希尔排序Shell Sort算法是插入排序算法的一种又叫作缩小增量排序Diminishing Increment Sort算法是插入排序算法的一种更高效的改进版本也是非稳定排序算法。希尔排序算法将数据序列按下标的一定增量进行分组对每组使用插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多在增量减至1时整个文件被分为一组算法终止。5.1、希尔排序算法的原理希尔排序算法的原理是先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全部记录依次进行直接插入排序。希尔排序算法的具体做法为假设待排序元素序列有N个元素则先取一个小于N的整数增量值increment作为间隔将全部元素分为increment个子序列将所有距离为increment的元素都放在同一个子序列中在每一个子序列中分别实行直接插入排序然后缩小间隔increment重复上述子序列的划分和排序工作直到最后取increment1将所有元素都放在同一个子序列中时排序终止。由于开始时increment的取值较大每个子序列中的元素较少所以排序速度较快到了排序后期increment的取值逐渐变小子序列中的元素个数逐渐增多但由于前面工作的基础大多数元素已经基本有序所以排序速度仍然很快。例如对数组[21,25,49,26,16,8]的排序过程如下。1第1趟排序。第1趟排序的间隔为“incrementN/313”​它将整个数据列划分为间隔为3的3个子序列然后对每个子序列都执行直接插入排序相当于对整个序列都执行了部分排序如图所示。2第2趟排序。第2趟排序的间隔为“incrementincrement/312”​将整个元素序列划分为两个间隔为2的子序列分别进行排序如图所示。3第3趟排序。第3趟排序的间隔为“incrementincrement/311”​在增量为1时说明整个数组已经完成排序。5.2、希尔排序算法的Java实现希尔排序算法的Java实现如下publicstaticint[]shellSort(int[]arr){intdkarr.length/31;while(dk1){ShellInsertSort(arr,dk);dkdk/31;}returnarr;}publicstaticvoidShellInsertSort(int[]a,intdk){//类似于插入排序算法但插入排序算法的增量是1这里的增量是dk将1换成dk即可for(intidk;ia.length;i){if(a[i]a[i-dk]){intj;intxa[i];//x为待插入的元素a[i]a[i-dk];for(ji-dk;j0xa[j];jj-dk){//通过循环逐个后移一位找到要插入的位置a[jdk]a[j];}a[jdk]x;//将数据插入对应的位置}}}6、归并排序算法归并排序算法是基于归并Merge操作的一种有效排序算法是采用分治法Divide and Conquer的典型应用。归并排序算法将待排序序列分为若干个子序列先对每个子序列进行排序等每个子序列都有序后再将有序子序列合并为整体的有序序列。若将两个有序表合并成一个有序表则称之为二路归并。6.1、归并排序算法的原理归并排序的原理是先将原始数组分解为多个子序列然后对每个子序列进行排序最后将排好序的子序列合并起来。如图5-8所示为对数组[4,1,3,9,6,8]进行归并排序先经过两次分解将数组分解成4个子序列然后对子序列数组进行排序和归并最终得到排好序的数组[1,3,4,6,8,9]​。6.2、归并排序算法的Java实现归并排序算法的Java实现如下publicstaticint[]mergeSort(int[]data){sort(data,0,data.length-1);returndata;}//对左右两边的数据进行递归publicstaticvoidsort(int[]data,intleft,intright){if(leftright)return;//找出中间索引intcenter(leftright)/2;//对左边的数组进行递归sort(data,left,center);//对右边的数组进行递归sort(data,center1,right);//将两个数组进行归并merge(data,left,center,right);}/ 将两个数组进行归并两个数组在归并前是有序数组在归并后依然是有序数组 paramdata数组对象left左边数组第1个元素的索引 center左边数组最后一个元素的索引center1是右边数组第1个元素的索引 right右边数组最后一个元素的索引 /publicstaticvoidmerge(int[]data,intleft,intcenter,intright){//临时数组int[]tmpArrnewint[data.length];//右边数组第1个元素的索引intmidcenter1;//third记录临时数组的索引intthirdleft;//缓存左边数组第1个元素的索引inttmpleft;while(leftcentermidright){//从两个数组中取出最小的值放入临时数组中if(data[left]data[mid]){tmpArr[third]data[left];}else{tmpArr[third]data[mid];}}//将剩余部分依次放入临时数组实际上两个while只会执行其中一个中while(midright){tmpArr[third]data[mid];}while(leftcenter){tmpArr[third]data[left];}//将临时数组中的内容复制到原数组中//原left-right范围内的内容被复制到原数组中while(tmpright){data[tmp]tmpArr[tmp];}}以上代码定了3个方法mergeSort()是归并排序方法的入口sort()对数据进行递归拆解和合并merge()进行数据排序和合并。其中sort()每次都将数组进行二分拆解然后对左侧的数组和右侧的数据分别进行递归。merge()先将数组进行冒泡排序然后依次将冒泡排序的结果放入临时数组中最后将排好序的临时数组放入排序数组中。7、桶排序算法桶排序Bucket Sort算法也叫作箱排序算法它将数组分到有限数量的桶中对每个桶再进行排序有可能使用其他排序算法或以递归方式继续使用桶排序进行排序​最后将各个桶合并。7.1、桶排序算法的原理桶排序算法的原理是先找出数组中的最大值和最小值并根据最大值和最小值定义桶然后将数据按照大小放入桶中最后对每个桶进行排序在每个桶的内部完成排序后就得到了完整的排序数组。如图所示为对数组[3,6,5,9,7,8]进行桶排序首先根据数据的长度和min、max创建三个桶分别为03、47、810然后将数组的数据按照相应的大小放入桶中接着将桶内部的数据分别进行排序最后将各个桶进行合并便得到了完整排序后的数组。7.2、桶排序算法的Java实现桶排序算法的Java实现如下publicstaticint[]bucketSort(int[]arr){intmaxInteger.MIN_VALUE;intminInteger.MAX_VALUE;for(inti0;iarr.length;i){maxMath.max(max,arr[i]);minMath.min(min,arr[i]);}//创建桶intbucketNum(max-min)/arr.length1;ArrayListArrayListIntegerbucketArrnewArrayList(bucketNum);for(inti0;ibucketNum;i){bucketArr.add(newArrayListInteger());}//将每个元素都放入桶中for(inti0;iarr.length;i){intnum(arr[i]-min)/(arr.length);bucketArr.get(num).add(arr[i]);}//对每个桶都进行排序for(inti0;ibucketArr.size();i){Collections.sort(bucketArr.get(i));}returnarr;}以上代码定义了bucketSort()的桶排序算法具体实现分为以下3步。在待排序数组中找出最大值max和最小值min并根据“bucketNummax-min/arr.length1”创建桶。遍历待排序的数组arr计算每个元素arr[i]的大小并放入桶中。对每个桶各自排序在每个桶的内部排序完成后就得到了完整的排序数组。8、基数排序算法基数排序Radix Sort算法是桶排序算法的扩展它将数据按位切割为不同的数字位数不够的补0然后在每个位数上分别进行比较最终得到排好序的序列。8.1、基数排序算法的原理基数排序算法的原理是将所有待比较数据统一为同一长度在位数不够时前面补零然后从低位到高位根据每个位上整数的大小依次对数据进行排序最终得到一个有序序列。如图所示为对数组[1,56,7,5,304,12,102,45,183,3,345,123]进行基数排序先将数组中的所有元素补为三位数并进行按位分割之后分别按照个位、十位、百位进行排序最终就得到了排序后的数组。8.2、基数排序算法的Java实现基数排序算法的Java实现如下//array数组 maxigit数组最大位数privatestaticint[]radixSort(int[]array,intmaxDigit){//数组最大位数的数据上限比如3位数的最大上限为1000doublemaxMath.pow(10,maxDigit1);intn1;//代表位数对应的数1,10,100……intk0;//保存每一位排序后的结果用于下一位的排序输入intlengtharray.length;//bucket用于保存每次排序后的结果将当前位上排序结果相同的数字放在同一个桶里int[][]bucketnewint[10][length];int[]ordernewint[length];//用于保存每个桶里有多少个数字while(nmax){for(intnum:array)//将数组array里的每个数字都放在相应的桶里{intdigit(num/n)%10;bucket[digit][order[digit]]num;order[digit];}//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果for(inti0;ilength;i){//在这个桶中有数据从上到下遍历这个桶并将数据保存到原数组中if(order[i]!0){for(intj0;jorder[i];j){array[k]bucket[i][j];k;}}order[i]0;//将桶中的计数器设置为0用于下一次位排序}n10;k0;//将k设置为0用于下一轮保存位排序结果}returnarray;}以上代码定义了名为radixSort()的基数排序方法在该方法中array为待排序数组maxDigit为数组的最大位数。并且在该方法中定义的max代表数组最大位数的数据上限用于控制while循环排序的趟次n代表位数个位为1十位为10; k保存每一位排序后的结果用于下一位的排序输入bucket数组为排序桶用于保存每次排序后的结果将当前位上排序结果相同的数字放在同一个桶里order数组用于保存每个桶里有多少个数字。具体做法是在while循环中先取出当前位的数据放入排序桶中然后将排序桶的数据覆盖到原数组中用于保存这一位的排序结果接着从上到下遍历这个桶并将数据保存到原数组中这样便完成了当前位的排序。假设数组最大有N位则进行N1次while循环便完成了所有位数个位、十位、百位……上的排序。9、其他算法9.1、剪枝算法剪枝算法属于算法优化范畴通过剪枝策略提前减少不必要的搜索路径。在搜索算法的优化中剪枝算法通过某种预判去掉一些不需要的搜索范围从直观上理解相当于剪去了搜索树中的某些“枝条”​故称剪枝。剪枝优化的核心是设计剪枝预判方法即哪些“枝条”被剪掉后可以缩小搜索范围提高搜索效率而又不影响整体搜索的准确性。如图所示为在二叉树的查找过程中提前判断元素48不可能在左侧树中将其剪枝以减少搜索范围。剪枝优化有三个原则正确、准确、高效。正确剪枝的前提是保证不丢失正确的结果。准确在保证正确性的基础上应该根据具体的问题采用合适的判断手段使不包含最优解的枝条尽可能多地被剪去以达到程序快速最优化的目的。剪枝是否准确是衡量优化算法优劣的标准。高效指尽可能减少搜索的次数使程序运行的时间减少。剪枝算法按照其判断思路可分为可行性剪枝和最优性剪枝。可行性剪枝该方法判断沿着某个路径能否搜索到数据如果不能则直接回溯。最优性剪枝又称上下界剪枝记录当前得到的最优值在当前节点无法产生比当前最优解更优的解时可以提前回溯。9.2、回溯算法回溯算法是一种最优选择搜索算法按选优条件向前搜索以达到目标。如果在探索到某一步时发现原先的选择并不是最优或达不到目标就退一步重新选择这种走不通就退回再走的方法叫作回溯法而满足回溯条件的某个状态的点叫作回溯点。如图所示为经历了[10,4,5,8]的线路后未找到需要的数据则回溯到根节点以另一条线路重新查找。9.3、最短路径算法最短路径算法指从某顶点出发沿着图的边到达另一顶点在途中可选的路径中各边上权值之和最小的一条路径叫作最短路径。解决最短路径问题的方法有Dijkstra算法、Bellman-Ford算法、Floyd算法和SPFA算法等。如图所示为从起点A到终点F有3条路径路径1为​[A, B, D, C]​路径2为​[A, F]​路径3为​[A, E, F]​。在各条边权重相等的情况下路径2显然为最短路径。最短路径算法的常见问题如下。确定起点的最短路径问题即已知起始节点求最短路径的问题适合使用Dijkstra算法。确定终点的最短路径问题已知终节点求最短路径的问题。在无向图中该问题与确定起点的问题等同在有向图中该问题与将所有路径方向反转以确定起点的问题等同。确定起点和终点的最短路径问题已知起点和终点求两节点之间的最短路径。全局最短路径问题求图中所有的最短路径适合使用Floyd-Warshall算法。