深度优先搜索具体操作是在得到一个新节点时立即遍历该新节点相邻的节点, 这样又得到一个新节点, 同理. 需要注意的是, 遍历过的节点不能被再次遍历. 如下: 从节点 0 出发开始遍历, 得到到新节点 6 时, 立马对新节点 6 进行遍历, 得到新节点 4; 如此反复以这种方式遍历新节点, 直到没有新节点了, 此时返回. 返回到根节点 0 的情况是, 继续对根节点 0 进行遍历, 得到新节点 2, 然后继续以上步骤. 从一个节点出发, 使用 DFS 对一个图进行遍历时, 能够遍历到的节点都是从初始节点可达的, DFS 常用来求解这种 可达性 问题. 1. 朋友圈 班上有 N 名学生. 其...

广度优先搜索具体操作是一层一层地进行遍历, 每层遍历都是以上一层遍历到的节点作为起点, 遍历其能访问到的所有节点. 需要注意的是, 遍历过的节点不能被再次遍历. 如下: 第一层: 0 -> {6, 2, 1, 5}; 第二层: 6 -> {4}; 2 -> {}; 1 -> {}; 5 -> {3} 第三层: 4 -> {}; 3 -> {} 每一层遍历的节点到根节点的距离都相同. 假设 di 表示第 i 个节点与根节点的距离, 可以推导出一个结论: 对于先遍历的节点 i 与后遍历的节点 j, 有 di <= dj. 利用这个结论, 可以...

插入排序过程中，序列分为已遍历部分和未遍历部分，已遍历序列有序，未遍历序列有序性未知，为了做到这一点，在每遍历每一个数时O(n)，依次在已遍历序列中从后往前比较O(n)，将当前数放入适当位置，直至未遍历部分为空O(n ^ 2)。相当于摸牌将牌组分为，手中的牌和牌组中的牌，手中的牌有序，牌组中的牌有序性未知，每摸一张牌将其插入合适位置，直至牌组为空。 一、插入排序 1、插入排序的实现 public static void insertSort(int[] arr, int start, int end) { for (int i = 1; i < arr.length; i...

快速排序也是使用分治策略，用partition函数将序列一分为二(O(n))后，将子序列递归排序((1 / n) * ∑[T(k) + T(n - k - 1)])，最后合并有序子序列(O(1))，T(n) = O(n) + (1 / n) * ∑[T(k) + T(n - k - 1)] = O(n * logn)。 一、快速排序 1、快速排序的实现 public static void quickSortCore(int[] arr, int lo, int hi) { if (lo < hi) { int mid = partition(ar...

归并排序使用分治策略，序列一分为二(O(1))后，将子序列递归排序(2 * T(n / 2))，最后合并有序子序列(O(n)),T(n) = 2 * T(n / 2) + O(n) = O(n * logn)。 一、归并排序 1、归并排序的实现 写递归函数就像开车，先系上安全带即先写出递归基。 public static void mergeSortCore(int[] arr, int lo, int hi) { if (lo == hi) { // <----- 安全带 return; } int mid = (...