第一部分：核心概念与理论基础
在深入具体的数据结构和算法之前,必须理解一些基础概念。
算法复杂度分析
这是评价算法好坏的黄金标准,是算法学习的基石。
-
时间复杂度：衡量算法执行时间随输入规模
n增长的趋势，我们使用“大O表示法”（Big-O Notation）来描述。O(1)- 常数时间：无论数据多大，执行时间都一样，数组通过索引访问元素。O(log n)- 对数时间：每次操作都将问题规模减半，二分查找。O(n)- 线性时间：执行时间与数据规模成正比，遍历数组。O(n log n)- 线性对数时间：非常高效的排序算法复杂度，归并排序、快速排序。O(n²)- 平方时间：嵌套循环，效率较低，简单的排序算法（冒泡、选择）。O(2ⁿ)- 指数时间：效率极低，通常用于解决组合问题，递归实现的斐波那契数列。O(n!)- 阶乘时间：效率极低，例如旅行商问题的暴力解法。
-
空间复杂度：衡量算法执行所需的额外内存空间随输入规模
n增长的趋势。O(1)- 常数空间：只使用了固定数量的变量。O(n)- 线性空间：需要与输入规模成正比的额外空间，创建一个与输入数组大小相同的辅助数组。
数据结构
数据结构是计算机中存储、组织数据的方式，好的数据结构能带来高效的算法。
第二部分：核心数据结构与Java实现
我们将按照“逻辑结构 -> 物理存储 -> Java实现 -> 操作分析”的顺序来学习。
线性结构
元素之间是一对一的关系。
a. 数组
-
逻辑结构：连续的内存空间，元素在内存中是连续存放的。
-
Java实现：
java.util.ArrayList是最常用的动态数组实现。
（图片来源网络，侵删）import java.util.ArrayList; ArrayList<String> list = new ArrayList<>(); list.add("Apple"); // 添加元素 list.add(0, "Banana"); // 在指定位置插入 String fruit = list.get(1); // 通过索引访问 O(1) list.remove("Apple"); // 删除元素 O(n) -
操作分析：
- 访问：
O(1)，直接通过地址偏移计算。 - 查找/插入/删除：
O(n)，最坏情况下需要遍历整个数组，插入和删除可能需要移动大量元素。
- 访问：
b. 链表
- 逻辑结构：元素在内存中不连续，通过指针（或引用）连接。
- Java实现：
java.util.LinkedList：双向链表实现。- 自定义单链表/双向链表节点：
// 单链表节点 class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } }
- 操作分析：
- 访问：
O(n)，必须从头节点开始遍历。 - 插入/删除：
O(1)，前提是已知节点位置，因为只需修改前后节点的指针即可，无需移动元素。
- 访问：
c. 栈
-
逻辑结构：后进先出。
-
Java实现：
-
java.util.Stack：已过时，不推荐。 -
java.util.LinkedList或java.util.ArrayDeque：推荐使用它们来实现栈的功能。import java.util.ArrayDeque; ArrayDeque<Integer> stack = new ArrayDeque<>(); stack.push(10); // 压栈 stack.push(20); int top = stack.peek(); // 查看栈顶元素 O(1) int popped = stack.pop(); // 弹出栈顶元素 O(1)
-
-
应用：函数调用栈、表达式求值、括号匹配、浏览器前进/后退。
d. 队列
-
逻辑结构：先进先出。
-
Java实现：
-
java.util.Queue：接口，不能直接实例化。 -
java.util.LinkedList或java.util.ArrayDeque：是实现Queue接口的常用类。 -
java.util.PriorityQueue：优先队列，基于堆实现，元素按优先级出队。import java.util.LinkedList; import java.util.Queue; Queue<String> queue = new LinkedList<>(); queue.offer("A"); // 入队 queue.offer("B"); String head = queue.peek(); // 查看队首元素 String dequeued = queue.poll(); // 出队
-
非线性结构
元素之间是一对多或多对多的关系。
a. 树
- 逻辑结构：分层结构，由节点和边组成。
- Java实现：通常需要自定义节点类。
// 二叉树节点 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } - 二叉树：每个节点最多有两个子节点（左、右）。
- 遍历：
- 深度优先：
- 前序遍历：根 -> 左 ->右
- 中序遍历：左 -> 根 -> 右 (二叉搜索树的中序遍历结果是升序的)
- 后序遍历：左 -> 右 -> 根
- 广度优先：层序遍历（使用队列实现）。
- 深度优先：
- 遍历：
- 二叉搜索树：左子树所有节点 < 根节点 < 右子树所有节点。
- 操作分析：平均情况下
O(log n)，最坏情况（树退化为链表）为O(n)。
- 操作分析：平均情况下
- 平衡二叉树：如AVL树、红黑树，通过旋转操作保持树的平衡，确保所有操作的最坏时间复杂度为
O(log n)。- Java实现：
java.util.TreeMap（红黑树）和java.util.TreeSet（基于红黑树）。
- Java实现：
- 堆：一种特殊的完全二叉树。
- 最大堆：父节点值 >= 子节点值。
- 最小堆：父节点值 <= 子节点值。
- Java实现：
java.util.PriorityQueue默认是最小堆。 - 应用：优先队列、堆排序。
b. 哈希表
-
逻辑结构：基于哈希函数实现，通过键直接计算出值的位置，实现
O(1)级别的查找。 -
Java实现：
java.util.HashMap和java.util.HashSet。HashMap：存储键值对。HashSet：存储不重复的元素。import java.util.HashMap; import java.util.HashSet;
HashMap<String, Integer> map = new HashMap<>(); map.put("Alice", 25); // 插入 map.put("Bob", 30); int age = map.get("Alice"); // 查找 O(1) 平均 map.remove("Bob"); // 删除
HashSet
set = new HashSet<>(); set.add(1); set.add(2); set.add(1); // 重复添加，无效 boolean contains = set.contains(2); // 查找 O(1) 平均 -
核心问题：
- 哈希冲突：两个不同的键通过哈希函数计算出相同的索引，解决方法有链地址法（Java 7之前）和开放地址法（Java 8之后，在冲突严重时会将链表转换为红黑树，
TreeNode）。
- 哈希冲突：两个不同的键通过哈希函数计算出相同的索引，解决方法有链地址法（Java 7之前）和开放地址法（Java 8之后，在冲突严重时会将链表转换为红黑树，
-
操作分析：平均
O(1)，最坏情况（所有键都冲突）为O(n)。
c. 图
- 逻辑结构：由顶点和边组成，用于表示多对多的关系。
- Java实现：没有内置的图类，通常需要自定义，常见表示方法：
- 邻接矩阵：二维数组，
matrix[i][j]表示顶点i和j之间是否有边，适合稠密图。 - 邻接表：数组 + 链表/哈希表。
array[i]存储一个链表，表示与顶点i相邻的所有顶点，适合稀疏图。
- 邻接矩阵：二维数组，
- 经典算法：
- 深度优先搜索：使用栈或递归实现。
- 广度优先搜索：使用队列实现。
- 最短路径算法：Dijkstra算法、Floyd-Warshall算法。
- 最小生成树算法：Prim算法、Kruskal算法。
第三部分：经典算法
排序算法
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 简单但效率低 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 每次找最小/大值 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 对小规模或基本有序数据高效 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 分治法，稳定高效 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 分治法，平均最快，应用最广 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 利用堆结构，原地排序 |
- Java实现：
java.util.Arrays.sort()对于基本类型使用双轴快速排序，对于对象使用归并排序（保证稳定性）。
查找算法
- 顺序查找：遍历数组，
O(n)。 - 二分查找：在有序数组中查找，
O(log n)。public int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 未找到 }
其他经典算法
- 递归与分治：将大问题分解成小问题解决，如归并排序、快速排序、斐波那契数列。
- 动态规划：通过存储子问题的解来避免重复计算，适用于最优解问题，如：背包问题、最长公共子序列、斐波那契数列。
- 贪心算法：在每一步都做出局部最优选择，期望最终得到全局最优解，如：Dijkstra算法、Prim算法、哈夫曼编码。
- 回溯算法：像走迷宫一样，在一个路径上探索，发现此路不通就回溯到上一步尝试其他选择，如：八皇后问题、全排列、数独。
第四部分：学习路径与实践建议
-
第一阶段：打好基础
- 目标：理解时间/空间复杂度，掌握数组和链表。
- 实践：用Java手写一个动态数组（
MyArrayList）和一个单链表（MyLinkedList），实现增删改查等基本操作。
-
第二阶段：深入核心数据结构
- 目标：掌握栈、队列、哈希表、树（重点是二叉树和二叉搜索树）。
- 实践：
- 用
LinkedList实现栈和队列。 - 手动实现一个简单的哈希表（处理哈希冲突用链地址法）。
- 手动实现二叉树,并实现前中后序遍历和层序遍历。
- 用
-
第三阶段：攻克经典算法
- 目标：熟练掌握各种排序和查找算法，理解其思想和代码实现。
- 实践：手写冒泡、选择、插入、归并、快速排序算法，分析它们的性能差异。
-
第四阶段：综合与应用
- 目标：学习动态规划、贪心、回溯等高级思想，并应用到图等复杂数据结构上。
- 实践：在LeetCode等平台上刷题，从“简单”题开始，逐步挑战“中等”和“困难”题。
推荐资源
- 书籍：
- 《算法（第4版）》：Robert Sedgewick & Kevin Wayne，Java语言描述，图文并茂，代码质量高，强烈推荐。
- 《数据结构与算法分析：Java语言描述》：Mark Allen Weiss，经典教材，理论分析透彻。
- 《剑指Offer》：国内面试神书，包含大量高质量面试题。
- 《LeetCode Cookbook》：按知识点分类的刷题指南。
- 在线课程：
- Coursera - "Algorithms, Part I & II"：普林斯顿大学Robert Sedgewek主讲，与《算法（第4版）》配套。
- 极客时间 - 《数据结构与算法之美》：国内高质量付费课程，讲解通俗易懂。
- 刷题网站：
- LeetCode：全球最大的刷题平台，面试必备。
- 牛客网：国内IT求职刷题社区，有大量公司真题。
学习数据结构与算法是一个循序渐进、理论与实践相结合的过程，不要只停留在看书和看视频，一定要亲手敲代码、分析复杂度、并在实际问题中应用，当你能熟练地运用这些知识来解决一个又一个LeetCode题目时，你会发现你的编程能力和解决问题的能力都得到了质的飞跃，祝你学习顺利！
