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]中查找key=20的数据，根据二分查找算法，只需查找两次便能命中数据。这里需要强调的是，二分查找算法要求要查找的集合是有序的，如果不是有序的集合，则先要通过排序算法排序后再进行查找。

1.2、二分查找算法的Java实现

二分查找算法的Java实现如下：

publicstaticintbinarySearch(int[]array,inta){intlow=0;inthigh=array.length-1;intmid;while(low<=high){mid=(low+high)/2;//中间位置if(array[mid]==a){returnmid;}elseif(a>array[mid]){//向右查找low=mid+1;}else{//向左查找high=mid-1;}}return-1;}

以上代码定义了方法binarySearch()用于二分查找，在该方法中有3个变量low、mid和high，分别表示二分查找的最小、中间和最大的数据索引。在以上代码中，通过一个while循环在数组中查找传入的数据，在该数据大于中间位置的数据时向右查找，即最大索引位置不变，将最小索引设置为上次循环的中间索引加1；在该数据小于中间位置的数据时向左查找，即最小索引位置不变，然后将最大索引设置为上次循环的中间索引并减1。重复以上过程，直到中间索引位置的数据等于要查找的数据，说明找到了要查找的数据，将该数据对应的索引返回。如果遍历到low>high还没有找到要查找的数据，则说明该数据在列表中不存在，返回-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(inti=0;i<arr.length-1;i++){//内层循环控制每一趟排序多少次for(intj=0;j<arr.length-1-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}returnarr;}

以上代码实现了一个名为bubbleSort()的冒泡排序算法，分为外层循环和内层循环，外层循环控制排序的次数，内层循环控制每一趟排序多少次。在内层循环中比较当前数据和下一个数据的大小，如果当前数据大于下一个数据，就交换二者的位置，这样重复进行判断，直至整个排序完成，最终返回排序后的数组。

3、插入排序算法

插入排序（Insertion Sort）算法是一种简单、直观且稳定的排序算法。如果要在一个已排好序的数据序列中插入一个数据，但要求此数据序列在插入数据后仍然有序，就要用到插入排序法。

插入排序的基本思路是将一个数据插入已经排好序的序列中，从而得到一个新的有序数据，该算法适用于少量数据的排序，是稳定的排序方法。

3.1、插入排序算法的原理

插入排序算法的原理如图5-3所示，类似于扑克牌游戏的抓牌和整理过程。在开始摸牌时，左手是空的。接着，每次从桌上摸起一张牌时，都根据牌的大小在左手扑克牌序列中从右向左依次比较，在找到第一个比该扑克牌大的位置时就将该扑克牌插入该位置的左侧，这样依次类推，无论什么时候，左手中的牌都是排好序的。

如图所示为插入排序算法的工作流程。输入原始数组[6, 2, 5, 8, 7 ]​，在排序时将该数组分成两个子集：一个是有序的L（left）子集，一个是无序的R（right）子集。初始时设L=[ 6 ], R = [ 2, 5, 8, 7 ]​。在L里面只有一个元素4，本身就是有序的。接着我们每次都从R中拿出一个元素插入L中从右到左比自己大的元素后面，然后将L中比自己大的所有元素整体后移，这样就保证了L子集仍然是有序的。重复以上插入操作，直到R子集的数据为空，这时整个数组排序完成，排序的结果被保存在L子集中。

3.2、插入排序算法的Java实现

插入排序算法的Java实现如下：

publicstaticint[]insertSort(intarr[]){for(inti=1;i<arr.length;i++){//插入的数intinsertVal=arr[i];//被插入的位置（准备和前一个数进行比较）intindex=i-1;//如果插入的数比被插入的数小while(index>=0&&insertVal<arr[index]){//则将arr[index]向后移动arr[index+1]=arr[index];//将index向前移动index--;}//将插入的数放入合适的位置arr[index+1]=insertVal;}returnarr;}

以上代码定义了insertSort()用于插入排序，其中，insertVal用于从数组中取出待插入的数据，index是待插入的位置。在insertSort()中通过while循环从数组中找到比待插入数据大的数据的索引位置index，然后将该index位置后的元素向后移动，接着将待插入的数据插入index+1的位置，如此重复，直到整个数组排序完成。

4、快速排序算法

快速排序（Quick Sort）是对冒泡排序的一种改进，通过一趟排序将要排序的数据序列分成独立的两部分，其中一部分的所有数据比另一部分的所有数据都要小，然后按此方法对两部分数据分别进行快速排序，整个排序过程递归进行，最终使整个数据序列变成有序的数据序列。

4.1、快速排序算法的原理

快速排序算法的原理是：选择一个关键值作为基准值（一般选择第1个元素为基准元素）​，将比基准值大的都放在右边的序列中，将比基准值小的都放在左边的序列中。具体的循环过程如下。

• 从后向前比较，用基准值和最后一个值进行比较。如果比基准值小，则交换位置；如果比基准值大，则继续比较下一个值，直到找到第1个比基准值小的值才交换位置。
• 在从后向前找到第1个比基准值小的值并交换位置后，从前向后开始比较。如果有比基准值大的，则交换位置；如果没有，则继续比较下一个，直到找到第1个比基准值大的值才交换位置。
• 重复执行以上过程，直到从前向后比较的索引大于等于从后向前比较的索引，则结束一次循环。这时对于基准值来说，左右两边都是有序的数据序列。
• 重复循环以上过程，分别比较左右两边的序列，直到整个数据序列有序。

如图所示是对数组[6,9,5,7,8]进行快速排序。先以第1个元素6为基准值，从数组的最后一位从后向前比较（比较顺序为：8>6、7>6、5<6）​，找到第1个比6小的数据5，然后进行第1次位置交换，即将数据6（索引为0）和数据5（索引为2）交换位置，之后基准值6位于索引2处；接着从前向后比较（比较顺序为：5<6、9>6）​，找到第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){intstart=low;//从前向后比较的索引intend=high;//从后向前比较的索引intkey=arr[low];//基准值while(end>start){//从后向前比较while(end>start&&arr[end]>=key)end--;//如果没有比基准值小的，则比较下一个，直到有比基准值小的，则交换位置，然后又从前向后比较if(arr[end]<=key){inttemp=arr[end];arr[end]=arr[start];arr[start]=temp;}//从前向后比较while(end>start&&arr[start]<=key)start++;//如果没有比基准值大的，则比较下一个，直到有比基准值大的，则交换位置if(arr[start]>=key){inttemp=arr[start];arr[start]=arr[end];arr[end]=temp;}//此时第1次循环比较结束，基准值的位置已经确定。左边的值都比关键值小，//右边的值都比关键值大，但是两边的顺序还有可能不一样，接着进行下面的递归调用}//递归左边序列：从第1个索引位置到“关键值索引-1”if(start>low)quickSort(arr,low,start-1);//递归右边序列：从“关键值索引+1”到最后一个位置if(end<high)quickSort(arr,end+1,high);returnarr;}

以上代码定义了名为quickSort()的快速排序方法，在该方法中定义了3个变量start、end和key，分别表示从前向后比较的索引、从后向前比较的索引和基准值。具体过程为：①通过while循环从后向前比较，找到比基准值小的，则交换位置；②通过while循环从前向后比较，找到比基准值大的，则交换位置；③根据从前向后比较的索引和从后向前比较的索引的大小不断递归调用，直到递归完成，返回排序后的结果。

5、希尔排序算法

希尔排序（Shell Sort）算法是插入排序算法的一种，又叫作缩小增量排序（Diminishing Increment Sort）算法，是插入排序算法的一种更高效的改进版本，也是非稳定排序算法。

希尔排序算法将数据序列按下标的一定增量进行分组，对每组使用插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，在增量减至1时，整个文件被分为一组，算法终止。

5.1、希尔排序算法的原理

希尔排序算法的原理是先将整个待排序的记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部记录依次进行直接插入排序。

希尔排序算法的具体做法为：假设待排序元素序列有N个元素，则先取一个小于N的整数增量值increment作为间隔，将全部元素分为increment个子序列，将所有距离为increment的元素都放在同一个子序列中，在每一个子序列中分别实行直接插入排序；然后缩小间隔increment，重复上述子序列的划分和排序工作，直到最后取increment=1，将所有元素都放在同一个子序列中时排序终止。

由于开始时increment的取值较大，每个子序列中的元素较少，所以排序速度较快；到了排序后期，increment的取值逐渐变小，子序列中的元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

例如，对数组[21,25,49,26,16,8]的排序过程如下。

（1）第1趟排序。第1趟排序的间隔为“increment=N/3+1=3”​，它将整个数据列划分为间隔为3的3个子序列，然后对每个子序列都执行直接插入排序，相当于对整个序列都执行了部分排序，如图所示。

（2）第2趟排序。第2趟排序的间隔为“increment=increment/3+1=2”​，将整个元素序列划分为两个间隔为2的子序列分别进行排序，如图所示。

（3）第3趟排序。第3趟排序的间隔为“increment=increment/3+1=1”​，在增量为1时，说明整个数组已经完成排序。

5.2、希尔排序算法的Java实现

希尔排序算法的Java实现如下：

publicstaticint[]shellSort(int[]arr){intdk=arr.length/3+1;while(dk==1){ShellInsertSort(arr,dk);dk=dk/3+1;}returnarr;}publicstaticvoidShellInsertSort(int[]a,intdk){//类似于插入排序算法，但插入排序算法的增量是1，这里的增量是dk，将1换成dk即可for(inti=dk;i<a.length;i++){if(a[i]<a[i-dk]){intj;intx=a[i];//x为待插入的元素a[i]=a[i-dk];for(j=i-dk;j>=0&&x<a[j];j=j-dk){//通过循环，逐个后移一位找到要插入的位置a[j+dk]=a[j];}a[j+dk]=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(left>=right)return;//找出中间索引intcenter=(left+right)/2;//对左边的数组进行递归sort(data,left,center);//对右边的数组进行递归sort(data,center+1,right);//将两个数组进行归并merge(data,left,center,right);}/＊＊ ＊ 将两个数组进行归并：两个数组在归并前是有序数组，在归并后依然是有序数组 ＊@paramdata：数组对象；left：左边数组第1个元素的索引； ＊ center左边数组最后一个元素的索引，center+1是右边数组第1个元素的索引 ＊ right：右边数组最后一个元素的索引 ＊/publicstaticvoidmerge(int[]data,intleft,intcenter,intright){//临时数组int[]tmpArr=newint[data.length];//右边数组第1个元素的索引intmid=center+1;//third记录临时数组的索引intthird=left;//缓存左边数组第1个元素的索引inttmp=left;while(left<=center&&mid<=right){//从两个数组中取出最小的值放入临时数组中if(data[left]<=data[mid]){tmpArr[third++]=data[left++];}else{tmpArr[third++]=data[mid++];}}//将剩余部分依次放入临时数组（实际上两个while只会执行其中一个）中while(mid<=right){tmpArr[third++]=data[mid++];}while(left<=center){tmpArr[third++]=data[left++];}//将临时数组中的内容复制到原数组中//（原left-right范围内的内容被复制到原数组中）while(tmp<=right){data[tmp]=tmpArr[tmp++];}}

以上代码定了3个方法：mergeSort()是归并排序方法的入口；sort()对数据进行递归拆解和合并；merge()进行数据排序和合并。其中，sort()每次都将数组进行二分拆解，然后对左侧的数组和右侧的数据分别进行递归。merge()先将数组进行冒泡排序，然后依次将冒泡排序的结果放入临时数组中，最后将排好序的临时数组放入排序数组中。

7、桶排序算法

桶排序（Bucket Sort）算法也叫作箱排序算法，它将数组分到有限数量的桶中，对每个桶再进行排序（有可能使用其他排序算法或以递归方式继续使用桶排序进行排序）​，最后将各个桶合并。

7.1、桶排序算法的原理

桶排序算法的原理是先找出数组中的最大值和最小值，并根据最大值和最小值定义桶，然后将数据按照大小放入桶中，最后对每个桶进行排序，在每个桶的内部完成排序后，就得到了完整的排序数组。

如图所示为对数组[3,6,5,9,7,8]进行桶排序，首先根据数据的长度和min、max创建三个桶，分别为0～3、4～7、8～10；然后将数组的数据按照相应的大小放入桶中；接着将桶内部的数据分别进行排序；最后将各个桶进行合并，便得到了完整排序后的数组。

7.2、桶排序算法的Java实现

桶排序算法的Java实现如下：

publicstaticint[]bucketSort(int[]arr){intmax=Integer.MIN_VALUE;intmin=Integer.MAX_VALUE;for(inti=0;i<arr.length;i++){max=Math.max(max,arr[i]);min=Math.min(min,arr[i]);}//创建桶intbucketNum=(max-min)/arr.length+1;ArrayList<ArrayList<Integer>>bucketArr=newArrayList(bucketNum);for(inti=0;i<bucketNum;i++){bucketArr.add(newArrayList<Integer>());}//将每个元素都放入桶中for(inti=0;i<arr.length;i++){intnum=(arr[i]-min)/(arr.length);bucketArr.get(num).add(arr[i]);}//对每个桶都进行排序for(inti=0;i<bucketArr.size();i++){Collections.sort(bucketArr.get(i));}returnarr;}

以上代码定义了bucketSort()的桶排序算法，具体实现分为以下3步。

• 在待排序数组中找出最大值max和最小值min，并根据“bucketNum=（max-min）/arr.length+1”创建桶。
• 遍历待排序的数组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位数的最大上限为1000doublemax=Math.pow(10,maxDigit+1);intn=1;//代表位数对应的数：1,10,100……intk=0;//保存每一位排序后的结果用于下一位的排序输入intlength=array.length;//bucket用于保存每次排序后的结果，将当前位上排序结果相同的数字放在同一个桶里int[][]bucket=newint[10][length];int[]order=newint[length];//用于保存每个桶里有多少个数字while(n<max){for(intnum:array)//将数组array里的每个数字都放在相应的桶里{intdigit=(num/n)%10;bucket[digit][order[digit]]=num;order[digit]++;}//将前一个循环生成的桶里的数据覆盖到原数组中，用于保存这一位的排序结果for(inti=0;i<length;i++){//在这个桶中有数据，从上到下遍历这个桶并将数据保存到原数组中if(order[i]!=0){for(intj=0;j<order[i];j++){array[k]=bucket[i][j];k++;}}order[i]=0;//将桶中的计数器设置为0，用于下一次位排序}n＊=10;k=0;//将k设置为0，用于下一轮保存位排序结果}returnarray;}

以上代码定义了名为radixSort()的基数排序方法，在该方法中array为待排序数组，maxDigit为数组的最大位数。并且，在该方法中定义的max代表数组最大位数的数据上限，用于控制while循环排序的趟次；n代表位数（个位为1，十位为10）; k保存每一位排序后的结果，用于下一位的排序输入；bucket数组为排序桶，用于保存每次排序后的结果，将当前位上排序结果相同的数字放在同一个桶里；order数组用于保存每个桶里有多少个数字。

具体做法是在while循环中先取出当前位的数据放入排序桶中，然后将排序桶的数据覆盖到原数组中用于保存这一位的排序结果，接着从上到下遍历这个桶并将数据保存到原数组中，这样便完成了当前位的排序。假设数组最大有N位，则进行N+1次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算法。