面试时的Java数据结构与算法.pdf

《面试时的Java数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《面试时的Java数据结构与算法.pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、面试时的 Java 数据结构与算法 查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始，如果这些问题回答不好，估计面试官都没有继续面试

2、下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握，有必要时要熟练写出代码。接下来我们就分析一下常见的排序算法及其使用场景。限于篇幅，某些算法的详细演示和图示请自行寻找详细的参考。冒泡排序 冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。举个栗子，对 5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4 和 6 比较，把 4 交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡

3、就完了，把最小的数 3 排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为 O(n2)。实现代码：/*Description:冒泡排序算法实现*author 王旭*/publicclassBubbleSort publicstaticvoidbubbleSort(intarr)if(arr=null|arr.length=0)return;for(inti=0;i)for(intj=arr.length-1;ji;j-)if(arrj)swap(arr,j-1,j);publicstaticvoidswap(intarr,inti,intj)inttemp=arri

4、;arri=arrj;arrj=temp;选择排序 选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对 5,3,8,6,4 这个无序序列进行简单选择排序，首先要选择 5 以外的最小数来和 5交换，也就是选择 3 和 5 交换，一次排序后就变成了 3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为 O(n2)。

5、实现代码：/*Description:简单选择排序算法的实现*author 王旭*/publicclassSelectSort publicstaticvoidselectSort(intarr)if(arr=null|arr.length=0)return;intminIndex=0;for(inti=0;i/只需要比较 n-1 次 minIndex=i;for(intj=i+1;j/从 i+1 开始比较，因为 minIndex 默认为 i 了，i 就没必要比了。if(arrjarrminIndex)minIndex=j;if(minIndex!=i)/如果 minIndex 不为 i，说明

6、找到了更小的值，交换之。swap(arr,i,minIndex);publicstaticvoidswap(intarr,inti,intj)inttemp=arri;arri=arrj;arrj=temp;插入排序 插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子，对 5,3,8,6,4 这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理

7、。然后 3 要插到 5 前面，把 5 后移一位，变成 3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后 8 不用动，6插在 8 前面，8 后移一位，4 插在 5 前面，从 5 开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是 O(n2)。实现代码：/*Description:简单插入排序算法实现*author 王旭*/publicclassInsertSort publicstaticvoidinsertSort(intarr)if(arr=null|arr.length=0)return;for(inti=1;i/假设第一个数位置时

8、正确的；要往后移，必须要假设第一个。intj=i;inttarget=arri;/待插入的/后移 while(j0&target)arrj=arrj-1;j-;/插入 arrj=target;快速排序 快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。举个栗子：对 5,3,8,6,4 这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。5,3,8,6

9、,4 用 5 作为比较的基准，最终会把 5 小的移动到 5 的左边，比 5 大的移动到 5 的右边。5,3,8,6,4 首先设置 i,j 两个指针分别指向两端，j 指针先扫描（思考一下为什么？）4 比5 小停止。然后 i 扫描，8 比 5 大停止。交换 i,j 位置。5,3,4,6,8 然后 j 指针再扫描，这时 j 扫描 4 时两指针相遇。停止。然后交换 4 和基准数。4,3,5,6,8 一次划分后达到了左边比 5 小，右边比 5 大的目的。之后对左右子序列递归排序，最终得到有序序列。上面留下来了一个问题为什么一定要 j 指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指

10、针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以 j 指针先移动才能先找到比基准数小的数。快速排序是不稳定的，其时间平均时间复杂度是 O(nlgn)。实现代码：/*Description:实现快速排序算法*author 王旭*/publicclassQuickSort/一次划分 publicstaticintpartition(intarr,intleft,intright)intpivotKey=arrleft;intpivotPointer=left;while(leftright)whi

11、le(left=pivotKey)right-;while(leftpivotKey)left+;swap(arr,left,right);/把大的交换到右边，把小的交换到左边。swap(arr,pivotPointer,left);/最后把 pivot 交换到中间 returnleft;publicstaticvoidquickSort(intarr,intleft,intright)if(left=right)return;intpivotPos=partition(arr,left,right);quickSort(arr,left,pivotPos-1);quickSort(arr,p

12、ivotPos+1,right);publicstaticvoidsort(intarr)if(arr=null|arr.length=0)return;quickSort(arr,0,arr.length-1);publicstaticvoidswap(intarr,intleft,intright)inttemp=arrleft;arrleft=arrright;arrright=temp;其实上面的代码还可以再优化，上面代码中基准数已经在 pivotKey 中保存了，所以不需要每次交换都设置一个 temp 变量，在交换左右指针的时候只需要先后覆盖就可以了。这样既能减少空间的使用还能降低赋

13、值运算的次数。优化代码如下：/*Description:实现快速排序算法*author 王旭*/publicclassQuickSort/*划分*paramarr*paramleft*paramright*return*/publicstaticintpartition(intarr,intleft,intright)intpivotKey=arrleft;while(leftright)while(left=pivotKey)right-;arrleft=arrright;/把小的移动到左边 while(leftpivotKey)left+;arrright=arrleft;/把大的移动到右

14、边 arrleft=pivotKey;/最后把 pivot 赋值到中间 returnleft;/*递归划分子序列*paramarr*paramleft*paramright*/publicstaticvoidquickSort(intarr,intleft,intright)if(left=right)return;intpivotPos=partition(arr,left,right);quickSort(arr,left,pivotPos-1);quickSort(arr,pivotPos+1,right);publicstaticvoidsort(intarr)if(arr=null|

15、arr.length=0)return;quickSort(arr,0,arr.length-1);总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。堆排序 堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。首先，实现堆排序需要解决两个问题：如何由一个无序序列键成一个堆？如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。第二个问题，怎么调整成堆？首先是将堆顶元素和

16、最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是 n/2 取底个元素，由此筛选即可。举个栗子：49,38,65,97,76,13,27,49 序列的堆排序建初始堆和调整的过程如下：实现代码：/*Description:堆排序算法的实现，以大顶堆为例。*author 王旭*/publicclassHeapSort/*堆筛选，除了 s

17、tart 之外，startend 均满足大顶堆的定义。*调整之后 startend 称为一个大顶堆。*paramarr 待调整数组*paramstart 起始指针*paramend 结束指针*/publicstaticvoidheapAdjust(intarr,intstart,intend)inttemp=arrstart;for(inti=2*start+1;i)/左右孩子的节点分别为 2*i+1,2*i+2/选择出左右孩子较小的下标 if(i)i+;if(temp=arri)break;/已经为大顶堆，=保持稳定性。arrstart=arri;/将子节点上移 start=i;/下一轮筛选

18、 arrstart=temp;/插入正确的位置 publicstaticvoidheapSort(intarr)if(arr=null|arr.length=0)return;/建立大顶堆 for(inti=arr.length/2;i=0;i-)heapAdjust(arr,i,arr.length-1);for(inti=arr.length-1;i=0;i-)swap(arr,0,i);heapAdjust(arr,0,i-1);publicstaticvoidswap(intarr,inti,intj)inttemp=arri;arri=arrj;arrj=temp;希尔排序 希尔排序

19、是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是 O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。举个栗子：从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一堂排序时的增量为 5，第二趟排序的增量为 3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键

20、字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当 n 在某个范围内时，时间复杂度可以达到 O(n1.3)。实现代码：/*Description:希尔排序算法实现*author 王旭*/publicclassShellSort/*希尔排序的一趟插入*paramarr 待排数组*paramd 增量*/publicstaticvoidshellInsert(inta

21、rr,intd)for(inti=d;i)intj=i-d;inttemp=arri;/记录要插入的数据 while(j=0&arrjtemp)/从后向前，找到比其小的数的位置 arrj+d=arrj;/向后挪动 j-=d;if(j!=i-d)/存在比其小的数 arrj+d=temp;publicstaticvoidshellSort(intarr)if(arr=null|arr.length=0)return;intd=arr.length/2;while(d=1)shellInsert(arr,d);d/=2;归并排序 归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以

22、理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。倒着来看，其实就是先两两合并，然后四四合并。最终形成有序序列。空间复杂度为 O(n)，时间复杂度为 O(nlogn)。举个栗子：实现代码：/*Description:归并排序算法的实现*author 王旭*/publicclassMergeSort publicstaticvoidmergeSort(intarr)mSort(arr,0,arr.length-1);/*递归分治*paramarr 待排数组*paramleft 左指针*paramr

23、ight 右指针*/publicstaticvoidmSort(intarr,intleft,intright)if(left=right)return;intmid=(left+right)/2;mSort(arr,left,mid);/递归排序左边 mSort(arr,mid+1,right);/递归排序右边 merge(arr,left,mid,right);/合并 /*合并两个有序数组*paramarr 待合并数组*paramleft 左指针*parammid 中间指针*paramright 右指针*/publicstaticvoidmerge(intarr,intleft,intmi

24、d,intright)/left,midmid+1,right inttemp=newintright-left+1;/中间数组 inti=left;intj=mid+1;intk=0;while(iright)if(arriarrj)tempk+=arri+;else tempk+=arrj+;while(imid)tempk+=arri+;while(jright)tempk+=arrj+;for(intp=0;p)arrleft+p=tempp;计数排序 如果在面试中有面试官要求你写一个 O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是 O(nlo

25、gn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。实现代码：/*Description:计数排序算法实现*author 王旭*/publicclassCountSort publicstaticvoidcountSort(intarr)if(arr=null|arr.length=0)return;intmax=max(arr);intcount=newintmax+1;Arrays.fill(count,0);for

26、(inti=0;i)countarri+;intk=0;for(inti=0;i)for(intj=0;j)arrk+=i;publicstaticintmax(intarr)intmax=Integer.MIN_VALUE;for(intele:arr)if(elemax)max=ele;returnmax;桶排序 桶排序算是计数排序的一种改进和推广，但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。桶排序的基本思想：假设有一组长度为 N 的待排关键字序列 K1.n。首先将这个序列划分成 M 个的子区间(桶)。然后基于某种映射函数，将待排序列的关键字 k 映射到第

27、 i 个桶中(即桶数组 B 的下标 i)，那么该关键字 k 就作为 Bi中的元素(每个桶 Bi都是一组大小为 N/M 的序列)。接着对每个桶 Bi 中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B0.BM中的全部内容即是一个有序序列。bindex=f(key)其中，bindex 为桶数组 B 的下标(即第 bindex 个桶),k 为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字 k1 举个栗子：假如待排序列 K=49、38、35、97、76、73、27、49。这些数据全部在 1100 之间。因此我们定制 10 个桶，然后确定映射函数 f(k

28、)=k/10。则第一个关键字 49 将定位到第 4 个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如图所示。只要顺序输出每个 Bi中的数据就可以得到有序序列了。桶排序分析：桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的 f(k)值的计算，其作用就相当于快排中划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。对 N 个关键字进行桶排序的时间复杂度分为两个部分：(1)循环计算每个关键字的桶映射函数，这个时间复杂度是 O(N)。(2)利用先进的

29、比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为O(Ni*logNi)。其中 Ni 为第 i 个桶的数据量。很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到 O(N*logN)了)。因此，我们需要尽量做到下面两点：(1)映射函数 f(k)能够将 N 个数据平均的分配到 M 个桶中，这样每个桶就有N/M个数据量。(2)尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪

30、费严重。这就是一个时间代价和空间代价的权衡问题了。对于 N 个待排数据，M 个桶，平均每个桶N/M个数据的桶排序平均时间复杂度为：O(N)+O(M(N/M)log(N/M)=O(N+N(logN-logM)=O(N+NlogN-N*logM)当 N=M 时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到 O(N)。总结：桶排序的平均时间复杂度为线性的 O(N+C)，其中 C=N*(logN-logM)。如果相对于同样的 N，桶数量 M 越大，其效率越高，最好的时间复杂度达到 O(N)。当然桶排序的空间复杂度为 O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是

31、昂贵的。此外，桶排序是稳定的。实现代码：/*Description:桶排序算法实现*author 王旭*/publicclassBucketSort publicstaticvoidbucketSort(intarr)if(arr=null&arr.length=0)return;intbucketNums=10;/这里默认为 10，规定待排数0,100)Listbuckets=newArrayList();/桶的索引 for(inti=0;i)buckets.add(newLinkedList();/用链表比较合适 /划分桶 for(inti=0;i)buckets.get(f(arri).

32、add(arri);/对每个桶进行排序 for(inti=0;i)if(!buckets.get(i).isEmpty()Collections.sort(buckets.get(i);/对每个桶进行快排 /还原排好序的数组 intk=0;for(Listbucket:buckets)for(intele:bucket)arrk+=ele;/*映射函数*paramx*return*/publicstaticintf(intx)returnx/10;基数排序 基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行

33、排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。举个栗子：实现代码：/*Description:基数排序算法实现*author 王旭*/publicclassRadixSort publicstaticvoidradixSort(intarr)if(arr=null&arr.length=0)ret

34、urn;intmaxBit=getMaxBit(arr);for(inti=1;i)Listbuf=distribute(arr,i);/分配 collecte(arr,buf);/收集 /*分配*paramarr 待分配数组*paramiBit 要分配第几位*return*/publicstaticListdistribute(intarr,intiBit)Listbuf=newArrayList();for(intj=0;j)buf.add(newLinkedList();for(inti=0;i)buf.get(getNBit(arri,iBit).add(arri);returnbuf

35、;/*收集*paramarr 把分配的数据收集到 arr 中*parambuf*/publicstaticvoidcollecte(intarr,Listbuf)intk=0;for(Listbucket:buf)for(intele:bucket)arrk+=ele;/*获取最大位数*paramx*return*/publicstaticintgetMaxBit(intarr)intmax=Integer.MIN_VALUE;for(intele:arr)intlen=(ele+).length();if(lenmax)max=len;returnmax;/*获取 x 的第 n 位，如果没有

36、则为 0.*paramx*paramn*return*/publicstaticintgetNBit(intx,intn)Stringsx=x+;if(sx.length()n)return0;else returnsx.charAt(sx.length()-n)-0;总结 在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。

37、但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。下面就总结一下排序算法的各自的使用场景和适用场合。从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在 n 较大时归并排序使用时间较少，但使用辅助空间较多。上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者 n 较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。基数排序的时间复杂度也可

38、以写成 O(d*n)。因此它最使用于 n 值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为 O(n2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。附：基于比较排序算法时间下限为 O(nlogn)的证明：基于比较排序

39、下限的证明是通过决策树证明的，决策树的高度（nlgn），这样就得出了比较排序的下限。首先要引入决策树。首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。先来说明一些二叉树的性质，令 T 是深度为 d 的二叉树，则 T 最多有 2片树叶。具有 L 片树叶的二叉树的深度至少是 logL。所以，对 n 个元素排序的决策树必然有 n!片树叶（因为 n 个数有 n!种不同的大小关系），所以 决 策 树 的 深 度 至 少 是log(n!)，即 至 少 需 要log(n!)次 比 较。而log(n!)=logn+log(n-1)+log(n-2)+log2+log1=logn+log(n-1)+log(n-2)+log(n/2)=(n/2)log(n/2)=(n/2)logn-n/2=O(nlogn)所以只用到比较的排序算法最低时间复杂度是 O(nlogn)。