《数据结构与算法核心精要：从基础到实战应用》

<｜begin▁of▁sentence｜># 1. 什么是数据结构 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 # 2. 什么是算法 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 # 3. 数据结构和算法的关系 - 数据结构是为算法服务的，算法要作用在特定的数据结构之上。 - 数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。 # 4. 学习重点 - 复杂度分析 - 最常用、最基础的数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树 - 最常用、最基础的算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法 # 5. 复杂度分析 ## 5.1. 大O复杂度表示法 大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。 ## 5.2. 时间复杂度分析 - 只关注循环执行次数最多的一段代码 - 加法法则：总复杂度等于量级最大的那段代码的复杂度 - 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 ## 5.3. 常见时间复杂度实例分析 - 常量阶 O(1) - 对数阶 O(logn) - 线性阶 O(n) - 线性对数阶 O(nlogn) - 平方阶 O(n^2)、立方阶 O(n^3) ... k次方阶 O(n^k) - 指数阶 O(2^n) - 阶乘阶 O(n!) ## 5.4. 空间复杂度分析 空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。 # 6. 数组 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 ## 6.1. 线性表 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。 ## 6.2. 非线性表 比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。 ## 6.3. 数组的优缺点 - 优点：支持随机访问，根据下标随机访问的时间复杂度为O(1) - 缺点：插入、删除操作效率低，平均情况时间复杂度为O(n) ## 6.4. 数组的插入操作 - 如果数组是有序的，那么插入操作需要移动元素，平均情况时间复杂度为O(n) - 如果数组是无序的，那么插入操作可以直接将新元素放到数组的末尾，时间复杂度为O(1) ## 6.5. 数组的删除操作 - 删除操作需要移动元素，平均情况时间复杂度为O(n) - 在某些特殊情况下，我们并不一定非得追求数组中数据的连续性。我们可以将多次删除操作集中在一起执行，这样可以提高删除的效率。 ## 6.6. 数组的访问越界问题 在C语言中，数组的访问越界是一种未定义行为，可能会导致程序崩溃。在Java中，数组的访问越界会抛出ArrayIndexOutOfBoundsException异常。 ## 6.7. 容器能否完全替代数组？ - 容器类（如Java中的ArrayList）的优势：支持动态扩容，提供了很多便利的API - 数组的优势：性能更好，支持基本数据类型，内存使用更高效 - 选择：如果数据大小事先已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组。或者表示多维数组时，用数组往往会更加直观。对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。 # 7. 链表 链表通过指针将一组零散的内存块串联起来使用。 ## 7.1. 单链表 - 每个节点除了存储数据之外，还需要记录链上的下一个节点的地址。 - 头节点：链表的第一个节点，用来记录链表的基地址。 - 尾节点：链表的最后一个节点，指向一个空地址NULL。 ## 7.2. 循环链表 循环链表是一种特殊的单链表，它的尾节点指向头节点，形成一个环。 ## 7.3. 双向链表 双向链表支持两个方向，每个节点有一个后继指针next指向后面的节点，还有一个前驱指针prev指向前面的节点。 ## 7.4. 双向循环链表 双向循环链表是循环链表和双向链表的结合体。 ## 7.5. 链表的优缺点 - 优点：插入、删除操作效率高，时间复杂度为O(1) - 缺点：随机访问效率低，时间复杂度为O(n) ## 7.6. 链表 vs 数组 - 数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。 - 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。 ## 7.7. 如何基于链表实现LRU缓存淘汰算法？ - 思路：我们维护一个有序单链表，越靠近链表尾部的节点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。 - 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的节点，并将其从原来的位置删除，然后再插入到链表的头部。 - 如果此数据没有在缓存链表中，又可以分为两种情况： - 如果此时缓存未满，则将此节点直接插入到链表的头部； - 如果此时缓存已满，则链表尾节点删除，将新的数据节点插入链表的头部。 ## 7.8. 如何轻松写出正确的链表代码？ - 理解指针或引用的含义 - 警惕指针丢失和内存泄漏 - 利用哨兵简化实现难度 - 重点留意边界条件处理 - 举例画图，辅助思考 - 多写多练，没有捷径 # 8. 栈 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 ## 8.1. 栈的实现 - 顺序栈：用数组实现的栈 - 链式栈：用链表实现的栈 ## 8.2. 栈的应用 - 函数调用栈 - 表达式求值 - 括号匹配 - 浏览器前进后退功能 ## 8.3. 栈的复杂度分析 - 入栈、出栈操作的时间复杂度都是O(1) - 空间复杂度是O(n) # 9. 队列 队列是一种“操作受限”的线性表，只允许在一端插入数据，在另一端删除数据。 ## 9.1. 队列的实现 - 顺序队列：用数组实现的队列 - 链式队列：用链表实现的队列 ## 9.2. 循环队列 循环队列可以解决顺序队列的“假溢出”问题。 ## 9.3. 阻塞队列和并发队列 - 阻塞队列：在队列为空的时候，从队头取数据会被阻塞。如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据。 - 并发队列：线程安全的队列。 ## 9.4. 队列的应用 - 线程池 - 消息队列 - 广度优先搜索 ## 9.5. 队列的复杂度分析 - 入队、出队操作的时间复杂度都是O(1) - 空间复杂度是O(n) # 10. 递归 递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等等。 ## 10.1. 递归需要满足的三个条件 - 一个问题的解可以分解为几个子问题的解 - 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 - 存在递归终止条件 ## 10.2. 如何编写递归代码？ 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 ## 10.3. 递归代码要警惕堆栈溢出 可以通过限制递归深度来解决。 ## 10.4. 递归代码要警惕重复计算 可以通过散列表来保存已经求解过的值。 ## 10.5. 怎么将递归代码改写为非递归代码？ 递归本身就是借助栈来实现的，所以我们可以用栈来模拟递归的过程。 ## 10.6. 递归的优缺点 - 优点：代码简洁、清晰 - 缺点：空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多 # 11. 排序 排序算法有很多种，最常用的有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。 ## 11.1. 排序算法的执行效率 - 最好情况、最坏情况、平均情况时间复杂度 - 时间复杂度的系数、常数 、低阶 - 比较次数和交换（或移动）次数 ## 11.2. 排序算法的内存消耗 - 原地排序（In-place）：特指空间复杂度是O(1)的排序算法。 - 非原地排序：空间复杂度不是O(1)的排序算法。 ## 11.3. 排序算法的稳定性 - 稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 - 稳定排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序。 - 不稳定排序算法：选择排序、快速排序、堆排序。 ## 11.4. 冒泡排序（Bubble Sort） - 思路：每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。 - 优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。 - 代码实现： ```java public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循环的标志位 boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j+1]) { // 交换 int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag = true; // 表示有数据交换 } } if (!flag) break; // 没有数据交换，提前退出 } } ``` - 分析： - 原地排序：是 - 稳定排序：是 - 时间复杂度：最好O(n)，最坏O(n^2)，平均O(n^2) ## 11.5. 插入排序（Insertion Sort） - 思路：我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。 - 代码实现： ```java public void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找插入的位置 for (; j >= 0; --j) { if (a[j] > value) { a[j+1] = a[j]; // 数据移动 } else { break; } } a[j+1] = value; // 插入数据 } } ``` - 分析： - 原地排序：是 - 稳定排序：是 - 时间复杂度：最好O(n)，最坏O(n^2)，平均O(n^2) ## 11.6. 选择排序（Selection Sort） - 思路：选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。 - 代码实现： ```java public void selectionSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n - 1; ++i) { // 查找最小值 int minIndex = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[minIndex]) { minIndex = j; } } // 交换 int tmp = a[i]; a[i] = a[minIndex]; a[minIndex] = tmp; } } ``` - 分析： - 原地排序：是 - 稳定排序：否 - 时间复杂度：最好O(n^2)，最坏O(n^2)，平均O(n^2) ## 11.7. 归并排序（Merge Sort） - 思路：归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 - 代码实现： ```java public void mergeSort(int[] a, int n) { mergeSortInternally(a, 0, n-1); } private void mergeSortInternally(int[] a, int p, int r) { if (p >= r) return; int q = p + (r - p)/2; // 分治递归 mergeSortInternally(a, p, q); mergeSortInternally(a, q+1, r); // 将A[p...q]和A[q+1...r]合并为A[p...r] merge(a, p, q, r); } private void merge(int[] a, int p, int q, int r) { int i = p; int j = q+1; int k = 0; // 初始化变量i, j, k int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组 while (i<=q && j<=r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } // 判断哪个子数组中有剩余的数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 将剩余的数据拷贝到临时数组tmp while (start <= end) { tmp[k++] = a[start++]; } // 将tmp中的数组拷贝回a[p...r] for (i = 0; i <= r-p; ++i) { a[p+i] = tmp[i]; } } ``` - 分析： - 原地排序：否 - 稳定排序：是 - 时间复杂度：最好O(nlogn)，最坏O(nlogn)，平均O(nlogn) - 空间复杂度：O(n) ## 11.8. 快速排序（Quick Sort） - 思路：快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。 - 代码实现： ```java public void quickSort(int[] a, int n) { quickSortInternally(a, 0, n-1); } private void quickSortInternally(int[] a, int p, int r) { if (p >= r) return; int q = partition(a, p, r); // 获取分区点 quickSortInternally(a, p, q-1); quickSortInternally(a, q+1, r); } private int partition(int[] a, int p, int r) { int pivot = a[r]; int i = p; for(int j = p; j < r; ++j) { if (a[j] < pivot) { if (i == j) { ++i; } else { int tmp = a[i]; a[i