【面试题】算法相关

1.冒泡排序

思想：比较相邻的元素。如果第一个比第二个大，就交换它们的值，从开始第一对到结尾的最后一对

代码实现：时间复杂度：O(n²)、空间复杂度：O(1)，稳定性：稳定。

public static void bubble(int[] array) { for (int i = 0; i < array.length - 1; i++) { for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } }

优化：加入标志性变量flag，标志某一趟排序过程中是否有数据交换，若没有，则已经有序。

2.简单选择排序

思想：每趟从待排序的记录中选出关键字最小的记录，放在最前面，直到全部排序结束为止。

代码实现：时间复杂度：O(n²)、空间复杂度：O(1)，稳定性：不稳定。

public void selectionSort(int[] arr) { // 需要遍历获得最小值的次数 // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列 for (int i = 0; i < arr.length - 1; i++) { int min = i; // 用来保存最小值得索引 // 寻找第i个小的数值 for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; } } // 若min有变化，就将找到的第i个小的数值与第i个位置上的数值交换 if (min != i) { int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } }

3.1 直接插入排序

思想：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

代码实现：时间复杂度：O(n²)、空间复杂度：O(1)，稳定性：稳定。

private static void insertSort(int[] data) { // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列 for (int i = 1; i < data.length; i++) { int temp = data[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置 int j = i - 1; // 只要当前比较的数(data[j])比temp小，就把这个数后移一位 while (j >= 0 && temp < data[j]) { data[j + 1] = data[j]; j--; } data[j + 1] = temp; } }

3.2 折半插入排序

思想：折半插入算法是对直接插入排序算法的改进，它通过“折半查找”在比较区查找插入点的位置，这样可以减少比较的次数，但移动的次数不变。

代码实现：时间复杂度：O(n²)、空间复杂度：O(1)，稳定性：稳定。

private static void binaryInsertSort(int[] a) { int n = a.length; int i,j; for(i=1;i<n;i++){ //temp为本次循环待插入有序列表中的数 int temp = a[i]; int low=0; int high=i-1; //寻找temp插入有序列表的正确位置，使用二分查找法 while(low <= high){ //有序数组的中间坐标，此时用于二分查找，减少查找次数 int mid = (low+high)/2; //若有序数组的中间元素大于待排序元素，则有序序列向中间元素之前搜索，否则向后搜索 if(a[mid]>temp){ high = mid-1; }else{ low = mid+1; } } for(j=i-1;j>=low;j--){ //元素后移，为插入temp做准备 a[j+1] = a[j]; } //插入temp a[low] = temp; } }

4.希尔排序（缩小增量排序）

思想：将待排序的数组元素分成多个子序列，对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后（步长逐渐减小为1），最后对所有元素进行一次直接插入排序。

代码实现：时间复杂度：O(nlog₂n)、空间复杂度：O(1)，稳定性：不稳定。

public static void shellSort(int[] data) { // 计算出最大的h值 int h = 1; while (h <= data.length / 3) { h = h * 3 + 1; } while (h >= 1) { for (int i = h; i < data.length; i += h) { if (data[i] < data[i - h]) { int tmp = data[i]; int j = i - h; while (j >= 0 && data[j] > tmp) { data[j + h] = data[j]; j -= h; } data[j + h] = tmp; } } // 计算出下一个h值 h = h / 3; } }

5.归并排序

思想：把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。即先将序列每次折半划分，再将划分后的序列段两两合并后排序。分治法的应用。

代码实现：时间复杂度：O(nlog₂n)、空间复杂度：O(n)，稳定性：稳定。

private static void mergeSort(int[] data,int start,int end) { //找出中间索引 int mid = (start + end) / 2; if (start < end) { //对左边数组进行递归 mergeSort(data, start, mid); //对右边数组进行递归 mergeSort(data, mid + 1, end); //合并 merge(data, start, mid, end); } } public static void merge(int[] data,int start,int mid,int end) { //用ArrayList来临时存放数组 List<Integer> list = new ArrayList<>(); //记录左边数组的第一个索引 int s = start; //记录右边数组的第一个索引 int index = mid + 1; while (start <= mid && index <= end) { //从两个数组中取出最小的放入ArrayList中 if (data[start] < data[index]) { list.add(data[start++]); } else { list.add(data[index++]); } } //左边剩余部分依次放入ArrayList中 while (start <= mid) { list.add(data[start++]); } //右边剩余部分依次放入ArrayList中 while (index <= end) { list.add(data[index++]); } //将ArrayList中的数值拷贝到原数组中 for (int datas : list) { data[s++] = datas; } }

6.快速排序

思想：数组中的每个元素与基准值比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程，直到排序结束。采取分而治之的思想。

代码实现：时间复杂度：O(nlog₂n)、空间复杂度：O(nlog₂n)，稳定性：不稳定。

public static void sort (int[] data , int left,int right) { if (left>right) { return; } //获取下次分割的基准标号 int mid = getMid(data,left,right); //对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序 sort(data,left,mid-1); //对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序 sort(data,mid+1,right); } public static int getMid(int[] data,int left,int right){ //以最左边的数为基准 int pivot = data[left]; while (left<right){ //从右端开始，向左遍历，直到找到小于pivot的数 while(left<right && data[right] > pivot){ right--; } //将比pivot小的元素放到最左边 data[left] = data[right]; //从左端开始，向右遍历，直到找到大于pivot的数 while(left<right && data[left] < pivot){ left++; } //将比pivot大的元素放到最右边 data[right] = data[left]; } //将pivot放到left的位置， data[left] = pivot; return left; } 优化：三者取中算法改进（固定值 或随机数）、优化小数组时的排序方案、优化递归操作。

7.堆排序

思想：

建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。

代码实现：时间复杂度：O(nlog₂n)、空间复杂度：O(1)，稳定性：不稳定。

//堆排序 static void sort(int[] datas){ creat(datas); for(int i = datas.length-1; i>0; i--){ swap(datas, 0, i); adjust(datas, 0, i); } } //创建大根堆 static void creat(int[] datas) { //找到第一个非叶子节点 for(int i = datas.length/2 - 1; i >= 0; i--){ adjust(datas, i, datas.length); } } //调整为大根堆 static void adjust(int[] datas, int root, int length) { //获得左子树 int left = 2*root+1; if (left >= length){ return; } //若右子树大于左子树，则取右孩子 if (left+1< length && datas[left] < datas[left + 1]){ left++; } //若左子树大于根节点，则互换值，再调整堆。 if(datas[root] < datas[left]){ swap(datas, root, left); adjust(datas,left,length); } } //数据交换 private static void swap(int[] datas, int i, int j){ int temp = datas[i]; datas[i] = datas[j]; datas[j] = temp; }

8.基数排序

思想：（桶排序）一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

代码实现（LSD）：时间复杂度：O(d(n+r))，r为基数，d为位数、空间复杂度：O®，稳定性：稳定。

public void radixSort(int[] list, int begin, int end, int digit) { final int radix = 10; // 基数 int i = 0, j = 0; int[] count = new int[radix]; // 存放各个桶的数据统计个数 int[] bucket = new int[end - begin + 1]; // 按照从低位到高位的顺序执行排序过程 for (int d = 1; d <= digit; d++) { // 置空各个桶的数据统计 for (i = 0; i < radix; i++) { count[i] = 0; } // 统计各个桶将要装入的数据个数 for (i = begin; i <= end; i++) { j = getDigit(list[i], d); count[j]++; } // count[i]表示第i个桶的右边界索引 for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } // 将数据依次装入桶中 // 这里要从右向左扫描，保证排序稳定性 for (i = end; i >= begin; i--) { // 求出关键码的第k位的数字， 例如：576的第3位是5 j = getDigit(list[i], d); // 放入对应的桶中，count[j]-1是第j个桶的右边界索引 bucket[count[j] - 1] = list[i]; // 对应桶的装入数据索引减一 count[j]--; } // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表 for (i = begin, j = 0; i <= end; i++, j++) { list[i] = bucket[j]; } } } public int[] sort(int[] list) { radixSort(list, 0, list.length - 1, 3); return list; }

9.八大排序算法的总结

当数据很小时，使用插入（数据有序）、简单选择、冒泡排序。

当数据规模一般时，使用快速排序（无序）、归并排序。

当数据规模很大时，使用归并（稳定）、桶排序。

排序算法参考链接：【程序员私房菜】一遍记住Java常用的八种排序算法与代码实现

10.RSA加密算法

随意选择两个大的质数p和q，p不等于q，计算N=pq。

根据欧拉函数，求得r = (p-1)(q-1)

选择一个小于 r 的整数 e，求得 e 关于模 r 的模反元素，命名为d。（模反元素存在，当且仅当e与r互质）

将 p 和 q 的记录销毁。

(N,e)是公钥，(N,d)是私钥。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。

RSA的缺点：产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；速度太慢：分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高；安全性，RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NP问题。

11.负载均衡

LB是一种服务器或网络设备的集群技术。负载均衡将特定的业务(网络服务、网络流量等)分担给多个服务器或网络设备，从而提高了业务处理能力，保证了业务的高可用性。

负载均衡策略：请求轮询、最少连接路由、ip哈希、

负载均衡的实例

http重定向：请求后返回一个新的URL，但有吞吐率限制、重定向访问深度不同的缺点

DNS负载均衡：为一个域名配置多个不同的IP地址，但DNS记录缓存不同

反向代理：用户和实际服务器中间人的角色，可以监控后端服务器，但需要一定开销。

IP负载均衡：工作在传输层的NAT服务器，可以修改发送来的IP数据包，将数据包的目标地址修改为实际服务器地址。

直接路由：工作在数据链路层，通过修改数据包的目标MAC地址（没有修改目标IP），将数据包转发到实际服务器上。

IP隧道：将调度器收到的IP数据包封装在一个新的IP数据包中，转交给实际服务器，然后实际服务器的响应数据包可以直接到达用户端

12.一致性哈希算法

一致性哈希的特点：平衡性、单调性、分散性、负载。

原理：将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1，可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置。从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

虚拟节点：解决在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜的问题。还可以解决因热点数据造成雪崩的问题，对热点区间进行划分，将挂掉的服务器的数据分配至其他服务器

13.KMP算法

KMP算法是当遇到不匹配字符时，根据前面已匹配的字符数和模式串前缀和后缀的最大相同字符串长度数组next的元素来确定向后移动的位数，预处理时间复杂度是O(m)，匹配时间复杂度是O(n)

KMP算法的核心就是求next数组，在字符串匹配的过程中，一旦某个字符匹配不成功，next数组就会指导模式串P到底该相对于S右移多少位再进行下一次匹配，从而避免无效的匹配。

next数组含义：代表在模式串P中，当前下标对应的字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表在模式串P中，下标为j的字符之前的字符串中有最大长度为k 的相同前缀后缀。

next数组求解方法：next[0] = -1。如果p[j] = p[k], 则next[j+1] = next[k] + 1; 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止

代码实现

public void KMPMatcher() { int n = text.length(); int m = pattern.length(); int prefix[] = computePrefix(); int q = 0; int count = 0; for(int i = 0; i < n; i++) { while(q > 0 && pattern.charAt(q)!= text.charAt(i)) { q = prefix[q -1]; } if(pattern.charAt(q) == text.charAt(i)) q++; if(q == m) { System.out.println("Pattern occurs with shift " + ++count + "times"); q = prefix[q - 1]; } } if(count == 0) { System.out.println("There is no matcher!"); } } //求解Next数组 private int[] computePrefix() { int length = pattern.length(); int[] prefix = new int[length]; prefix[0] = 0; int k = 0; for(int i = 1; i < length; i++) { while(k > 0 && pattern.charAt(k) != pattern.charAt(i)) { k = prefix[k -1]; } if(pattern.charAt(k) == pattern.charAt(i)) k++; prefix[i] = k; } return prefix; } //求解Next数组的另一种方法 protected int[] getNext(char[] p) { // 已知next[j] = k,利用递归的思想求出next[j+1]的值 // 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下: // 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1; // 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1, // 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止 int pLen = p.length; int[] next = new int[pLen]; int k = -1; int j = 0; next[0] = -1; // next数组中next[0]为-1 while (j < pLen - 1) { //k表示前缀的单个字符，j表示后缀的单个字符 if (k == -1 || p[j] == p[k]) { k++; j++; next[j] = k; } else { //k回溯 k = next[k]; } } return next; }

KMP参考链接：从头到尾彻底理解KMP

本人才疏学浅，若有错，请指出，谢谢！ 如果你有更好的建议，可以留言我们一起讨论，共同进步！ 衷心的感谢您能耐心的读完本篇博文！