一. 最小生成树算法

• 连通图：在无向图 G 中，若从顶点 i 到顶点 j 有路径，则称顶点 i 和顶点 j 是连通的。若图 G 中任意两个顶点都连通，则称 G 为连通图。

• 生成树：一个连通图的生成树是该连通图的一个极小连通子图，它含有全部顶点，但只有构成一个数的(n-1)条边。

• 最小生成树：对于一个带权连通无向图 G 中的不同生成树，各树的边上的 权值之和最小。构造最小生成树的准则有三条：

• 必须只使用该图中的边来构造最小生成树。

• 必须使用且仅使用(n-1)条边来连接图中的 n 个顶点。

• 不能使用产生回路的边。

1. Prim 算法

假设 G=(V,E)是一个具有 n 个顶点的带权连通无向图，T(U,TE)是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，则由 G 构造从起始顶点 v 出发的最小生成树 T 的步骤为：

• 初始化 U={v}，以 v 到其他顶点的所有边为候选边(U 中所有点到其他顶点的边)。

• 重复以下步骤(n-1)次，使得其他(n-1)个顶点被加入到 U 中。

• 从候选边中挑选权值最小的边加入 TE，设该边在 V-U(这里是集合减)中的顶点是 k，将 k 加入 U 中。

• 考察当前 V-U 中的所有顶点 j，修改候选边，若边(k,j)的权值小于原来和顶点 j 关联的候选边，则用(k,j)取代后者作为候选边。

2. Kruskal 算法

假设 G=(V,E)是一个具有 n 个顶点的带权连通无向图，T(U,TE)是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，则由 G 构造从起始顶点 v 出发的最小生成树 T 的步骤为：

• 置 U 的初始值等于 V(即包含 G 中的全部顶点)，TE 的初始值为空

• 将图 G 中的边按权值从小到大的顺序依次选取，若选取的边未使生成树 T 形成回路，则加入 TE，否则放弃，知道 TE 中包含(n-1)条边为止。

二. 最短路径算法

1. Dijkstra —— 贪心算法

从一个顶点到其余顶点的最短路径

设 G=(V,E)是一个带权有向图，把图中顶点集合 V 分成两组，第 1 组为已求出最短路径的顶点（用 S 表示，初始时 S 只有一个源点，以后每求得一条最短路径 v,...k，就将 k 加到集合 S 中，直到全部顶点都加入 S）。第 2 组为其余未确定最短路径的顶点集合（用 U 表示），按最短路径长度的递增次序把第 2 组的顶点加入 S 中。

步骤：

1. 初始时，S 只包含源点，即 S={v}，顶点 v 到自己的距离为 0。U 包含除 v 外的其他顶点，v 到 U 中顶点 i 的距离为边上的权。

2. 从 U 中选取一个顶点 u，顶点 v 到 u 的距离最小，然后把顶点 u 加入 S 中。

3. 以顶点 u 为新考虑的中间点，修改 v 到 U 中各个点的距离。

4. 重复以上步骤知道 S 包含所有顶点。

2. Floyd —— 动态规划

Floyd 算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题。该算法的时间复杂度为 $$O(N^{3})$$，空间复杂度为 $$O(N^{2})$$

设 $$D_{i,j,k}$$为从 $$i$$到 $$j$$的只以 $$(1..k)$$集合中的节点为中间节点的最短路径的长度。

$$ D{i,j,k}=\begin{cases} D{i,j,k-1} &最短路径不经过 k D{i,k,k-1}+D{k,j,k-1} &最短路径经过 k \end{cases} $$

因此，$$D{i,j,k}=min(D{i,k,k-1}+D{k,j,k-1},D{i,j,k-1})$$。伪代码描述如下：

// let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) // the weight of the edge (u,v)for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if

三. KMP 算法

KMP 算法解决的问题是字符匹配，这个算法把字符匹配的时间复杂度缩小到 O(m+n),而空间复杂度也只有 O(m),n 是 target 的长度，m 是 pattern 的长度。

• 部分匹配表（Next 数组）：表的作用是 让算法无需多次匹配 S 中的任何字符。能够实现线性时间搜索的关键是 在不错过任何潜在匹配的情况下，我们”预搜索”这个模式串本身并将其译成一个包含所有可能失配的位置对应可以绕过最多无效字符的列表。

• Next 数组（前缀和前缀的比较）：t 为模式串，j 为下标

• Next[0] = -1

• Next[j] = MAX{ k | 0 < k < j | " t0 t1 ... tk " = "t ( j-k ) t ( j-k+1 ) ... t( j-1 )" }

|i| 0| 1| 2| 3| 4| 5 |6| |–| | t[i]| A| B| C| D| A| B| D| |next[i]| -1| 0 |0 |0 |0 |1 |2|

• NextVal 数组：是一种优化后的 Next 数组，是为了解决类似 aaaab 这种模式串的匹配，减少重复的比较。 如果 t[next[j]]=t[j]：nextval[j]=nextval[next[j]]，否则 nextval[j]=next[j]。

|i| 0| 1| 2| 3| 4| 5 |6| |–| | t | a| b| c| a| b| a |a| |next[j] | -1| 0 |0 |0 |1 |2 |1| |nextval[j] | -1| 0 |0 |-1 |0 |2 |1|

在上面的表格中，t[next[4]]=t[4]=b，所以 nextval[4]=nextval[next[4]]=0

四. 查找算法

1. ASL

由于查找算法的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数（平均查找长度）作为衡量一个查找算法效率的标准。ASL= ∑(n,i=1) Pi*Ci，其中 n 为元素个数，Pi 是查找第 i 个元素的概率，一般为 Pi=1/n，Ci 是找到第 i 个元素所需比较的次数。

2. 顺序查找

原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。时间复杂度 o(n)。

3. 折半查找

折半查找要求线性表是有序表。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为 O(log n)。

• 可以借助二叉判定树求得折半查找的平均查找长度：log2(n+1)-1。

• 折半查找在失败时所需比较的关键字个数不超过判定树的深度，n 个元素的判定树的深度和 n 个元素的完全二叉树的深度相同 log2(n)+1。

public int binarySearchStandard(int[] num, int target){ int start = 0; int end = num.length - 1; while(start <= end){ //注意1 int mid = start + ((end - start) >> 1); if(num[mid] == target) return mid; else if(num[mid] > target){ end = mid - 1; //注意2 } else{ start = mid + 1; //注意3 } } return -1;}

• 如果是 start < end，那么当 target 等于 num[num.length-1]时，会找不到该值。

• 因为 num[mid] > target, 所以如果有 num[index] == target, index 一定小于 mid，能不能写成 end = mid 呢？举例来说：num = {1, 2, 5, 7, 9}; 如果写成 end = mid，当循环到 start = 0, end = 0 时（即 num[start] = 1, num[end] = 1 时），mid 将永远等于 0，此时 end 也将永远等于 0，陷入死循环。也就是说寻找 target = -2 时，程序将死循环。

• 因为 num[mid] < target, 所以如果有 num[index] == target, index 一定大于 mid，能不能写成 start = mid 呢？举例来说：num = {1, 2, 5, 7, 9}; 如果写成 start = mid，当循环到 start = 3, end = 4 时（即 num[start] = 7, num[end] = 9 时），mid 将永远等于 3，此时 start 也将永远等于 3，陷入死循环。也就是说寻找 target = 9 时，程序将死循环。

4. 分块查找

分块查找又称索引顺序查找，它是一种性能介于顺序查找和折半查找之间的查找方法。分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

五. 排序算法

1. 常见排序算法

稳定排序：

• 冒泡排序 — O(n²)

• 插入排序 — O(n²)

• 桶排序 — O(n); 需要 O(k) 额外空间

• 归并排序 — O(nlogn); 需要 O(n) 额外空间

• 二叉排序树排序 — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间

• 基数排序 — O(n·k); 需要 O(n) 额外空间

不稳定排序：

• 选择排序 — O(n²)

• 希尔排序 — O(nlogn)

• 堆排序 — O(nlogn)

• 快速排序 — O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

2. 交换排序

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序总的平均时间复杂度为 O(n^2)。冒泡排序是一种稳定排序算法。 - 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 - 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 - 针对所有的元素重复以上的步骤，除了最后一个。 - 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

void bubble_sort(int a[], int n){ int i, j, temp; for (j = 0; j < n - 1; j++) for (i = 0; i < n - 1 - j; i++) { if(a[i] > a[i + 1]) { temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; } }}

快速排序

快速排序是一种 不稳定 的排序算法，平均时间复杂度为 O(nlogn)。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为：

• 从数列中挑出一个元素，称为”基准”（pivot），

• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快排的时间花费主要在划分上，所以 - 最坏情况：时间复杂度为 O(n^2)。因为最坏情况发生在每次划分过程产生的两个区间分别包含 n-1 个元素和 1 个元素的时候。 - 最好情况：每次划分选取的基准都是当前无序区的中值。如果每次划分过程产生的区间大小都为 n/2，则快速排序法运行就快得多了。

public void sort(int[] arr, int low, int high) { int l = low; int h = high; int povit = arr[low]; while (l < h) { while (l < h && arr[h] >= povit) h--; if (l < h) { arr[l] = arr[h]; l++; } while (l < h && arr[l] <= povit) l++; if (l < h) { arr[h] = arr[l]; h--; } } arr[l] = povit; System.out.print("l=" + (l + 1) + ";h=" + (h + 1) + ";povit=" + povit + "n"); System.out.println(Arrays.toString(arr)); if (l - 1 > low) sort(arr, low, l - 1); if (h + 1 < high) sort(arr, h + 1, high); }

快排的优化

1. 当待排序序列的长度分割到一定大小后，使用插入排序。

2. 快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化。优化后，可以缩减堆栈深度，由原来的 O(n)缩减为 O(logn)，将会提高性能。

3. 从左、中、右三个数中取中间值。

3. 插入排序

直接插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为 O(n^2)。是稳定的排序方法。 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

void insert_sort(int* a, int len) { for (int i = 1; i < len; ++i) { int j = i - 1; int temp = a[i]; while (j >= 0 && temp < a[j]) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; }}

希尔排序

也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

void shell_sort(int* a, int len) { int step = len / 2; int temp; while (step > 0) { for (int i = step; i < len; ++i) { temp = a[i]; int j = i - step; while (j >= 0 && temp < a[j]) { a[j + step] = a[j]; j -= step; } a[j + step] = temp; } step /= 2; }}

4. 选择排序

直接选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。实际适用的场合非常罕见。

void selection_sort(int arr[], int len) { int i, j, min, temp; for (i = 0; i < len - 1; i++) { min = i; for (j = i + 1; j < len; j++) if (arr[min] > arr[j]) min = j; temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; }}

堆排序

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。

1. 将数组分为有序区和无序区，在无序区中建立最大堆

2. 将堆顶的数据与无序区末尾的数据交换

3. 从后往前，直到所有数据排序完成

public void heapSort(int[] nums) { for (int i = nums.length - 1; i >= 0; i--) { maxHeap(nums, 0, i); swap(nums, 0, i); }}public void maxHeap(int[] heap, int start, int end) { if (start == end) { return; } int parent = start; int childLeft = start * 2 + 1; int childRight = childLeft + 1; if (childLeft <= end) { maxHeap(heap, childLeft, end); if (heap[childLeft] > heap[parent]) { swap(heap, parent, childLeft); } } if (childRight <= end) { maxHeap(heap, childRight, end); if (heap[childRight] > heap[parent]) { swap(heap, parent, childRight); } }}private void swap(int[] nums, int a, int b) { int t = nums[a]; nums[a] = nums[b]; nums[b] = t;}

5. 归并排序

归并排序采用分治的思想： - Divide：将 n 个元素平均划分为各含 n/2 个元素的子序列； - Conquer：递归的解决俩个规模为 n/2 的子问题； - Combine：合并俩个已排序的子序列。

性能：时间复杂度总是为 O(NlogN)，空间复杂度也总为为 O(N)，算法与初始序列无关，排序是稳定的。

public void mergeSort(int[] array, int start, int end, int[] temp) { if (start >= end) { return; } int mid = (start + end) / 2; mergeSort(array, start, mid, temp); mergeSort(array, mid + 1, end, temp); int f = start, s = mid + 1; int t = 0; while (f <= mid && s <= end) { if (array[f] < array[s]) { temp[t++] = array[f++]; } else { temp[t++] = array[s++]; } } while (f <= mid) { temp[t++] = array[f++]; } while (s <= end) { temp[t++] = array[s++]; } for (int i = 0, j = start; i < t; i++) { array[j++] = temp[i]; }}

6. 基数排序

对于有 d 个关键字时，可以分别按关键字进行排序。有俩种方法： - MSD：先从高位开始进行排序，在每个关键字上，可采用基数排序 - LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

即通过每个数的每位数字的大小来比较

//找出最大数字的位数int maxNum(int arr[], int len) { int _max = 0; for (int i = 0; i < len; ++i) { int d = 0; int a = arr[i]; while (a) { a /= 10; d++; } if (_max < d) { _max = d; } } return _max;}void radixSort(int *arr, int len) { int d = maxNum(arr, len); int *temp = new int[len]; int count[10]; int radix = 1; for (int i = 0; i < d; ++i) { for (int j = 0; j < 10; ++j) { count[j] = 0; } for (int k = 0; k < len; ++k) { count[(arr[k] / radix) % 10]++; } for (int l = 1; l < 10; ++l) { count[l] += count[l - 1]; } for (int m = 0; m < len; ++m) { int index = (arr[m] / radix) % 10; temp[count[index] - 1] = arr[m]; count[index]--; } for (int n = 0; n < len; ++n) { arr[n] = temp[n]; } radix *= 10; } delete (temp);}

7. 拓扑排序

在有向图中找拓扑序列的过程，就是拓扑排序。拓扑序列常常用于判定图是否有环。

• 从有向图中选择一个入度为 0 的结点，输出它。

• 将这个结点以及该结点出发的所有边从图中删除。

• 重复前两步，直到没有入度为 0 的点。

如果所有点都被输出，即存在一个拓扑序列，则图没有环。

写在最后

以上就是笔者整理的一些算法面试题；当然，要想拿大厂的 offer 光靠这些可不西行哟，像 Kafka、Mysql、Tomcat、Docker、Spring、MyBatis、Nginx、Netty、Dubbo、Redis、Netty、Spring cloud、分布式、高并发、性能调优、微服务等架构技术至少也要掌握各七八十才行！

针对以上的技术点呢，笔者也整理了一套视频学习资料和面试题

原文档打开方式：我的学习笔记