1、面试时地Java大数据结构与算法面试时的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 王旭 */public class BubbleSort public static void bubbleSort(int arr) if(arr = null | arr.length = 0) return ; for(int i=0; i) for(int j=arr.length-1; ji; j-) if(arrj ) swap(arr, j-1, j); public static v
4、oid swap(int arr, int i, int j) int temp = arri; arri = arrj; arrj = temp; 选择排序选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定
5、了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n2)。实现代码：/* *Description:简单选择排序算法的实现 *author 王旭 */public class SelectSort public static void selectSort(int arr) if(arr = null | arr.length = 0) return ; int minIndex = 0; for(int i=0; i/只需要比较n-1次 minIndex = i; for(int j=i+1; j/从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
6、if(arrj arrminIndex) minIndex = j; if(minIndex != i) /如果minIndex不为i，说明找到了更小的值，交换之。 swap(arr, i, minIndex); public static void swap(int arr, int i, int j) int temp = arri; arri = arrj; arrj = temp; 插入排序插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一
7、个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n2)。实现代码：/* *Description:简单插入排序算法实现 *author 王旭 */public class InsertSort public sta
8、tic void insertSort(int arr) if(arr = null | arr.length = 0) return ; for(int i=1; i/假设第一个数位置时正确的；要往后移，必须要假设第一个。 int j = i; int target = arri; /待插入的 /后移 while(j 0 & target ) arrj = arrj-1; j -; /插入 arrj = target; 快速排序快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小
9、的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。5,3,8,6,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大
10、的目的。之后对左右子序列递归排序，最终得到有序序列。上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。实现代码：/* *Description:实现快速排序算法 *author 王旭 */public class QuickSort /一次划分 public static int partition
11、(int arr, int left, int right) int pivotKey = arrleft; int pivotPointer = left; while(left right) while(left = pivotKey) right -; while(left pivotKey) left +; swap(arr, left, right); /把大的交换到右边，把小的交换到左边。 swap(arr, pivotPointer, left); /最后把pivot交换到中间 return left; public static void quickSort(int arr,
12、int left, int right) if(left = right) return ; int pivotPos = partition(arr, left, right); quickSort(arr, left, pivotPos-1); quickSort(arr, pivotPos+1, right); public static void sort(int arr) if(arr = null | arr.length = 0) return ; quickSort(arr, 0, arr.length-1); public static void swap(int arr,
13、int left, int right) int temp = arrleft; arrleft = arrright; arrright = temp; 其实上面的代码还可以再优化，上面代码中基准数已经在pivotKey中保存了，所以不需要每次交换都设置一个temp变量，在交换左右指针的时候只需要先后覆盖就可以了。这样既能减少空间的使用还能降低赋值运算的次数。优化代码如下：/* *Description:实现快速排序算法 *author 王旭 */public class QuickSort /* * 划分 * param arr * param left * param right * r
14、eturn */ public static int partition(int arr, int left, int right) int pivotKey = arrleft; while(left right) while(left = pivotKey) right -; arrleft = arrright; /把小的移动到左边 while(left pivotKey) left +; arrright = arrleft; /把大的移动到右边 arrleft = pivotKey; /最后把pivot赋值到中间 return left; /* * 递归划分子序列 * param a
15、rr * param left * param right */ public static void quickSort(int arr, int left, int right) if(left = right) return ; int pivotPos = partition(arr, left, right); quickSort(arr, left, pivotPos-1); quickSort(arr, pivotPos+1, right); public static void sort(int arr) if(arr = null | arr.length = 0) retu
16、rn ; quickSort(arr, 0, arr.length-1); 总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。堆排序堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。首先，实现堆排序需要解决两个问题：如何由一个无序序列键成一个堆？如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较
17、当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。举个栗子：49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：实现代码：/* *Description:堆排序算法的实现，以大顶堆为例。 *author 王旭 */public class HeapSort /* * 堆筛选，除了start之外，
18、startend均满足大顶堆的定义。 * 调整之后startend称为一个大顶堆。 * param arr 待调整数组 * param start 起始指针 * param end 结束指针 */ public static void heapAdjust(int arr, int start, int end) int temp = arrstart; for(int i=2*start+1; i) /左右孩子的节点分别为2*i+1,2*i+2 /选择出左右孩子较小的下标 if(i ) i +; if(temp = arri) break; /已经为大顶堆，=保持稳定性。 arrstart
19、= arri; /将子节点上移 start = i; /下一轮筛选 arrstart = temp; /插入正确的位置 public static void heapSort(int arr) if(arr = null | arr.length = 0) return ; /建立大顶堆 for(int i=arr.length/2; i=0; i-) heapAdjust(arr, i, arr.length-1); for(int i=arr.length-1; i=0; i-) swap(arr, 0, i); heapAdjust(arr, 0, i-1); public static
20、 void swap(int arr, int i, int j) int temp = arri; arri = arrj; arrj = temp; 希尔排序希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。举个栗子：从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录
21、组成一个子序列。如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n1.3)。实现代码：/* *Description:希尔排序算法实现 *author 王旭 */public
22、 class ShellSort /* * 希尔排序的一趟插入 * param arr 待排数组 * param d 增量 */ public static void shellInsert(int arr, int d) for(int i=d; i) int j = i - d; int temp = arri; /记录要插入的数据 while (j=0 & arrjtemp) /从后向前，找到比其小的数的位置 arrj+d = arrj; /向后挪动 j -= d; if (j != i - d) /存在比其小的数 arrj+d = temp; public static void sh
23、ellSort(int arr) if(arr = null | arr.length = 0) return ; int d = arr.length / 2; while(d = 1) shellInsert(arr, d); d /= 2; 归并排序归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。倒着来看，其实就是先两两合并，然后四四合并。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。举个栗子：
24、实现代码：/* *Description:归并排序算法的实现 *author 王旭 */public class MergeSort public static void mergeSort(int arr) mSort(arr, 0, arr.length-1); /* * 递归分治 * param arr 待排数组 * param left 左指针 * param right 右指针 */ public static void mSort(int arr, int left, int right) if(left = right) return ; int mid = (left + ri
25、ght) / 2; mSort(arr, left, mid); /递归排序左边 mSort(arr, mid+1, right); /递归排序右边 merge(arr, left, mid, right); /合并 /* * 合并两个有序数组 * param arr 待合并数组 * param left 左指针 * param mid 中间指针 * param right 右指针 */ public static void merge(int arr, int left, int mid, int right) /left, mid mid+1, right int temp = new i
26、ntright - left + 1; /中间数组 int i = left; int j = mid + 1; int k = 0; while(i right) if(arri arrj) tempk+ = arri+; else tempk+ = arrj+; while(i mid) tempk+ = arri+; while(j right) tempk+ = arrj+; for(int p=0; p) arrleft + p = tempp; 计数排序如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlo
27、gn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。实现代码：/* *Description:计数排序算法实现 *author 王旭 */public class CountSort public static void countSort(int arr) if(arr = null | arr.length = 0) return ; int max = max(arr); int count = new intma
28、x+1; Arrays.fill(count, 0); for(int i=0; i) countarri +; int k = 0; for(int i=0; i) for(int j=0; j) arrk+ = i; public static int max(int arr) int max = Integer.MIN_VALUE; for(int ele : rr) if(ele max) max = ele; return max; 桶排序桶排序算是计数排序的一种改进和推广，但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。桶排序的基本思想：假设有一组长度为N的待排关键字序列K1.n。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为Bi中的元素(每个桶Bi都是一组大小为N/M的序列)。接着对每个桶Bi中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B0.BM中的全部内容即是一个有序序列。bindex=f(key) 其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1举个栗子：假如待排序列K=
