数据结构与算法基础

发表于 2026-06-29 分类于教程， AI训练师

系统讲解数据结构与算法核心知识，涵盖数组、链表、栈、队列、树、图、哈希表及排序查找算法，补充链表逆置、快慢指针等重点知识的具体操作步骤，适合人工智能训练师系统学习及算法基础复习。

这是”人工智能训练师基础”系列拆出来的第一篇独立讲义。在原系列里，数据结构和算法是核心内容，概念密集、细节多，容易在这里混淆细节。所以把它单独拎出来，专门补上了原文只点了名字、没讲怎么操作的那些算法——比如链表逆置怎么转指针、快慢指针到底怎么走、二分查找的边界为什么那样写、堆排序怎么从数组建堆。每一段都配上输入输出示例，让你能跟着走一遍，”听明白、能做题”。复习时这一篇和原系列对照着看，遗忘的部分能很快捡回来。

第一章数据结构与算法：把数据摆明白，把套路用清楚

数据结构和算法是重点内容，概念点特别密集，关键就靠你对细节的拿捏。

线性表：数组与链表的取舍

线性表是最基础的结构，元素排成一条线，元素之间是一对一的前后关系。这一节的真正重点不在”什么是线性表”，而在它的两种物理实现——数组和链表——各自的取舍。

数组，是连续内存里的一排座位，下标就是座位号。最大的好处是随机访问快，下标一给就能直接算出地址，时间复杂度 O(1)。代价是插入和删除很麻烦，中间插一个，后面所有人都要往后挪一个位置，O(n)。而且数组要事先定好大小，开多了浪费、开少了溢出。

链表正好反过来，内存不连续，靠指针把节点串起来，像一场寻宝游戏，每个节点只告诉你”下一个在哪”。它的好处是插入删除快，只要改几个指针就行，O(1) 就能搞定（前提是你已经站在了要操作的位置）。代价是访问慢，想拿第 100 个节点，得从头一个一个顺着指针走过去，O(n)。

这一组对比非常重要，记住一句话就够：”数组擅长查、链表擅长增删”。再延伸几个易混点：单链表只能往后走，双向链表前后都能走，循环链表尾节点指回头部。链表常见的算法有逆置、找中点（快慢指针）、判断是否有环（快慢指针追及），这几个套路一定要熟。下面就把这三个套路的具体操作步骤拆开讲。

链表逆置：三指针法

逆置链表最经典的写法是用三个指针：prev、curr、next。核心思路是”一边遍历一边把每个节点的 next 指针掉头指向前一个”。prev 记前一个节点，curr 记当前节点，next 临时存下一个节点（因为等会儿要改 curr.next，不改的话就找不到下一个了）。

操作步骤很机械，背下来就行：

第一步，初始化：prev = None，curr = head（头节点）。
第二步，循环，只要 curr 不是 None：

先把 next = curr.next 存起来（不然改完指针就找不到下一个了）
再把 curr.next = prev（这一步就是掉头，让当前节点指向前一个）
然后 prev = curr（prev 往前走一步）
最后 curr = next（curr 往前走一步）
第三步，循环结束（curr 是 None 时），prev 就是新链表的头，返回 prev。

代码长这样：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr is not None:
        next_node = curr.next  # 先存下一个，别丢了
        curr.next = prev      # 掉头，指向前一个
        prev = curr           # prev 前进一步
        curr = next_node      # curr 前进一步
    return prev              # 循环结束时 prev 就是新头

输入输出示例。输入链表 1 -> 2 -> 3 -> 4 -> 5 -> None，走一遍：

初始 prev=None, curr=1
第 1 轮：next=2，1.next=None，prev=1，curr=2。链表变成 None<-1 2->3->4->5
第 2 轮：next=3，2.next=1，prev=2，curr=3。变成 None<-1<-2 3->4->5
第 3 轮：next=4，3.next=2，prev=3，curr=4。变成 None<-1<-2<-3 4->5
第 4 轮：next=5，4.next=3，prev=4，curr=5。变成 None<-1<-2<-3<-4 5
第 5 轮：next=None，5.next=4，prev=5，curr=None。变成 None<-1<-2<-3<-4<-5
循环结束，返回 prev=5

最终输出链表 5 -> 4 -> 3 -> 2 -> 1 -> None，逆置成功。

快慢指针找中点

找链表中点用快慢指针，思路是”快的跑得快，慢的跑得慢，快的跑到尾时慢的正好在中点”。慢指针每次走一步，快指针每次走两步，快指针走到尾（None 或 next 是 None）时停下，慢指针所在位置就是中点。

具体步骤：

第一步，slow = fast = head，两个指针都从头出发。
第二步，循环条件是 fast 不是 None 且 fast.next 不是 None（保证快指针还能走两步）：

slow = slow.next（走一步）
fast = fast.next.next（走两步）
第三步，循环结束时 slow 就是中点。

代码：

def findMiddle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

输入输出示例。输入链表 1 -> 2 -> 3 -> 4 -> 5：

初始 slow=1, fast=1
第 1 轮：slow=2, fast=3
第 2 轮：slow=3, fast=5
第 3 轮检查条件：fast.next 是 None，退出循环
返回 slow=3，正好是中点

偶数个节点的情况，输入 1 -> 2 -> 3 -> 4 -> 5 -> 6：

初始 slow=1, fast=1
第 1 轮：slow=2, fast=3
第 2 轮：slow=3, fast=5
第 3 轮：slow=4, fast=None
第 4 轮检查条件：fast 是 None，退出
返回 slow=4

注意，偶数个时返回的是后半段的第一个节点（4），不是前半段的末尾（3）。这取决于循环条件用 fast 还是 fast.next 判空，写法不同中点偏向也不同，选定一种写法别来回切。

快慢指针判断是否有环

判断链表有没有环也是快慢指针，但这里要的是”追及”——如果有环，快指针迟早会从后面追上慢指针；如果无环，快指针会先走到尾。

具体步骤：

第一步，slow = fast = head。
第二步，循环条件还是 fast 不是 None 且 fast.next 不是 None：

slow = slow.next（走一步）
fast = fast.next.next（走两步）
每走一步检查 slow == fast，相等就说明追上了，返回 True（有环）
第三步，循环正常结束（快指针走到尾了都没追上），返回 False（无环）。

代码：

def hasCycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True   # 相遇了，有环
    return False          # 快指针走到头，无环

输入输出示例。假设链表是 1 -> 2 -> 3 -> 4 -> 5，并且 5 的 next 指回 3（形成 3->4->5->3 的环）：

初始 slow=1, fast=1
第 1 轮：slow=2, fast=3，不相等
第 2 轮：slow=3, fast=5，不相等
第 3 轮：slow=4, fast=4（fast 从 5 走两步，先到 3 再到 4），相等！返回 True

为什么一定能追上？因为快指针每轮比慢指针多走一步，在有环里每轮两者的距离缩小 1，迟早归零。这是弗洛伊德龟兔赛跑算法，名字记一下就行。

栈与队列：一个后进先出，一个先进先出

栈和队列本质上是”操作受限的线性表”，只能在特定位置进出，正是因为受限，才有了独特的性质。

栈是后进先出，缩写 LIFO，最形象的生活类比就是食堂里叠盘子，最后放上去的那个最先被拿走。它只允许在栈顶一端操作，进栈叫 push，出栈叫 pop。栈的典型应用场景你最好能背下来几个：函数调用（递归就是靠栈实现的）、括号匹配、表达式求值、浏览器的前进后退。看到”回退””撤销””配对””嵌套”这类词，第一反应就应该是栈。

队列是先进先出，缩写 FIFO，类比排队买饭，先来的先服务。一端进（队尾 enqueue）、一端出（队头 dequeue）。队列最典型的应用是广度优先搜索（BFS）和各种排队调度场景。

这里有个容易混淆的点是循环队列。普通队列用数组实现时，队头出队后会留下空位却用不上，这叫”假溢出”。循环队列把数组首尾相连解决这问题，但判空判满要小心：通常约定牺牲一个单元，当 front==rear 时判空，当 (rear+1)%size==front 时判满，队列长度公式是 (rear-front+size)%size。这一串公式容易记混，建议记住”牺牲一个单元”这个核心思路，公式现场推。

再补一个重点：给定一个入栈序列，判断某个出栈序列是否合法，这是经典问题。规律是随时可以出栈，但一旦出栈的元素不能”插回去”，合法性判定要会模拟。栈的合法出栈序列数量遵循卡特兰数【需网络查询确认：卡特兰数公式 C(n)=C(2n,n)/(n+1)】。

树：从二叉树到红黑树

树是层次结构，一对多，像家谱或公司组织架构。重点是二叉树这一支，往上延伸到 B 树和红黑树。

先说二叉树本身，每个节点最多两个子节点。两个常见概念必须分清：满二叉树是”每个节点都有两个子节点，且所有叶子在同一层”，整棵树长得严丝合缝；完全二叉树是”除最后一层外都满，最后一层从左到右连续排”，允许最后一层没排满，但不允许中间有空缺。这两个词看着像，差别就在”满”和”连续”上。

二叉树的遍历是核心中的核心，四种方式要倒背如流：前序（根左右）、中序（左根右）、后序（左右根）、层序（按层从左到右）。一个经典重点是：前序加中序可以唯一确定一棵二叉树，后序加中序也可以，但前序加后序不行。原因是前序和后序都能确定根，但只有中序能区分左右子树。

二叉树四种遍历：用一棵具体的树走一遍

光说”根左右、左根右”容易迷糊，咱们拿一棵具体的二叉树实际走一遍。这棵树长这样（用文字画出来）：

也就是节点 1 是根，左孩子 2、右孩子 3；节点 2 左孩子 4、右孩子 5；节点 3 没有左孩子、右孩子 6；节点 5 左孩子 7、没有右孩子。

前序遍历（根左右）：先访问根，再访问左子树，再访问右子树。

访问 1
进左子树（以 2 为根）：访问 2，进 2 的左子树访问 4（4 是叶子），回来到 2 的右子树（以 5 为根）：访问 5，进 5 的左子树访问 7
进右子树（以 3 为根）：访问 3，3 没有左孩子，进右子树访问 6
结果是 1, 2, 4, 5, 7, 3, 6

中序遍历（左根右）：先访问左子树，再访问根，再访问右子树。

1 的左子树是 2 那一支：先访问 2 的左子树（4），再访问 2，再访问 2 的右子树（5 那一支：先访问 5 的左子树 7，再访问 5）
访问根 1
1 的右子树是 3 那一支：3 没有左子树，访问 3，再访问 3 的右子树（6）
结果是 4, 2, 7, 5, 1, 3, 6

后序遍历（左右根）：先访问左子树，再访问右子树，最后访问根。

1 的左子树（2 那一支）：先访问 4，再访问 2 的右子树（5 那一支：先访问 7，再访问 5），最后访问 2
1 的右子树（3 那一支）：3 没有左子树，访问右子树 6，最后访问 3
最后访问根 1
结果是 4, 7, 5, 2, 6, 3, 1

层序遍历（按层从左到右）：用队列，从根开始一层一层往下。

第 0 层：1
第 1 层：2, 3
第 2 层：4, 5, 6
第 3 层：7
结果是 1, 2, 3, 4, 5, 6, 7

代码写出来对照着看：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 构造上面那棵树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
root.left.right.left = TreeNode(7)

# 前序：根左右
def preorder(node):
    if node is None:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

# 中序：左根右
def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

# 后序：左右根
def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

# 层序：队列辅助的 BFS
from collections import deque
def levelorder(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return result

print(preorder(root))   # [1, 2, 4, 5, 7, 3, 6]
print(inorder(root))    # [4, 2, 7, 5, 1, 3, 6]
print(postorder(root))  # [4, 7, 5, 2, 6, 3, 1]
print(levelorder(root)) # [1, 2, 3, 4, 5, 6, 7]

把上面四个结果背下来，遇到求某棵树的遍历序列就能照着套。

再往上走是二叉搜索树（BST），它的规则是”左子树都小于根，右子树都大于根”，中序遍历正好得到有序序列。问题是它可能退化成一条链，查找变成 O(n)，所以才需要平衡。

B 树是多路搜索树，和二叉树的根本区别在于”矮胖”：每个节点可以存多个关键字、有多个子节点，整棵树高度很低。它是专门为磁盘这种”按块读取”的设备设计的，目的是减少磁盘 IO 次数，所以常用于数据库索引和文件系统。m 阶 B 树的约束是每个节点最多 m 个子节点、最多 m-1 个关键字，根节点之外的内部节点至少 ⌈m/2⌉ 个子节点。这一段约束记个大概即可，重点理解”为什么 B 树矮、为什么适合磁盘”。

红黑树是自平衡的二叉搜索树，它不像 AVL 树那样严格平衡，而是放宽约束：保证最长路径不超过最短路径的两倍，从而在查找和增删之间取折中。它的五条性质最好能背下来：第一，节点非红即黑；第二，根节点是黑；第三，叶子节点（NIL 空节点）是黑；第四，红节点的孩子必须是黑（也就是不能有连续两个红）；第五，从任一节点到其所有叶子节点的路径，黑节点数量相同，这个数叫黑高。红黑树插入和删除后的调整靠”变色加旋转”，具体调整规则比较繁琐，记住”靠变色和左右旋来恢复性质”就够了。红黑树的典型应用包括 Java 的 TreeMap 和 TreeSet、Linux 内核的进程调度（CFS）【需网络查询确认：epoll 内部使用的具体数据结构版本细节】。

顺带说一个对比重点：AVL 树比红黑树更严格平衡，查询多、增删少的场景用 AVL 更划算；增删频繁的场景用红黑树更划算。这是个容易混淆的判断点。

另外二叉树还有几个性质公式要记牢：叶子节点数 n0 等于度为 2 的节点数 n2 加 1，即 n0 = n2 + 1；n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1。

图：邻接矩阵与邻接表

图是比树更一般的结构，顶点之间的关系是多对多，任意两个点都能连。图分无向图、有向图，边还可以带权。要会区分度、入度、出度：无向图谈度，有向图分开谈入度和出度。

图的存储方式是这一节的重点，两种必须都会。

邻接矩阵是用一个 n×n 的二维数组，matrix[i][j]=1 表示顶点 i 到 j 有边，带权图就把 1 换成权值。它的优点是查边特别快，O(1) 就能判断两点之间有没有边；缺点是空间占用固定 O(n²)，无论边多边少都占这么多。所以邻接矩阵适合稠密图（边特别多的情况）。无向图的邻接矩阵一定是对称的，这是容易混淆的判断点。

邻接表是每个顶点挂一个链表，链表里存它的所有邻居。它的优点是省空间，只存实际存在的边，适合稀疏图；缺点是判断两点之间有没有边要遍历链表，不能一步到位。

对比记忆：稠密用矩阵、稀疏用邻接表。空间上，邻接矩阵 O(n²)，邻接表 O(n+e)（n 是顶点数、e 是边数）。无向图邻接表中所有链表节点数之和是 2e，有向图是 e。

哈希表：用空间换时间的典范

哈希表是”用空间换时间”这句话的最佳注脚。它通过一个哈希函数，把 key 直接映射到数组下标，所以查找、插入、删除平均都能做到 O(1)，这是其他结构比不了的。

哈希函数最常见的是除留余数法，H(key) = key mod p，其中 p 通常选一个不大于表长的质数。这一步不是重点，重点在冲突处理。

冲突是不可避免的，因为不同的 key 可能算出同一个地址。解决冲突主要有两大流派。第一类是开放定址法，冲突了就去寻找下一个空位，具体有线性探测（往后一个一个找）、二次探测（按平方跳跃着找）。第二类是链地址法，也叫拉链法，把映射到同一地址的所有元素挂成一个链表。两种方法各有特点：开放定址法容易产生”聚集”现象（连续占用一长串），拉链法处理起来直观但要多存指针。

哈希表冲突处理：线性探测和拉链法的具体操作

光说”往后找空位””挂链表”还是抽象，咱们拿一组数实际插一遍。设表长 7，哈希函数 H(key) = key mod 7，插入序列是 15, 8, 1, 22, 16, 9。

先算每个 key 的初始地址：15 mod 7 = 1，8 mod 7 = 1，1 mod 7 = 1，22 mod 7 = 1，16 mod 7 = 2，9 mod 7 = 2。前四个都映射到位置 1，后两个映射到位置 2，冲突很多，正好演示冲突处理。

线性探测法（开放定址法的一种）的规则是：算出地址 a，如果 a 被占了，就看 a+1，再被占就看 a+2，依此类推，找到第一个空位就放进去（超过表尾要回绕）。

按这个规则插入：

插 15：地址 1，位置 1 空，直接放。表变成 [_, 15, _, _, _, _, _]
插 8：地址 1，位置 1 有 15，看位置 2，空，放 8。表变成 [_, 15, 8, _, _, _, _]
插 1：地址 1，位置 1 有 15，位置 2 有 8，位置 3 空，放 1。表变成 [_, 15, 8, 1, _, _, _]
插 22：地址 1，位置 1、2、3 都被占，位置 4 空，放 22。表变成 [_, 15, 8, 1, 22, _, _]
插 16：地址 2，位置 2 有 8，位置 3 有 1，位置 4 有 22，位置 5 空，放 16。表变成 [_, 15, 8, 1, 22, 16, _]
插 9：地址 2，位置 2、3、4、5 都被占，位置 6 空，放 9。表变成 [_, 15, 8, 1, 22, 16, 9]

最终线性探测的结果是 [空, 15, 8, 1, 22, 16, 9]。注意看位置 1 到位置 6 连成一片，这就是”聚集”现象——后面插进来的元素探测距离越来越长，性能变差。

拉链法（链地址法）的规则是：算出地址 a，如果 a 这个位置已经有元素，就把新元素挂到 a 的链表末尾。

按这个规则插入：

插 15：地址 1，链表空，挂上。位置 1：15 -> null
插 8：地址 1，已经有 15，挂到链表尾。位置 1：15 -> 8 -> null
插 1：地址 1，链表是 15->8，挂尾。位置 1：15 -> 8 -> 1 -> null
插 22：地址 1，挂尾。位置 1：15 -> 8 -> 1 -> 22 -> null
插 16：地址 2，位置 2 链表空，挂上。位置 2：16 -> null
插 9：地址 2，已经有 16，挂尾。位置 2：16 -> 9 -> null

最终拉链法的结果是位置 1 挂着 15->8->1->22，位置 2 挂着 16->9，其它位置空。拉链法没有聚集问题，但代价是每个元素要多存一个 next 指针。

查找时也一样：算出地址后，线性探测要顺着往后找直到找到目标或遇到空位（说明不存在）；拉链法只要顺着链表往下找就行。这一组示例搞懂了，要算某个元素的探测次数或查找长度，照着模拟就行。

一个重点知识是装填因子（也叫负载因子），它等于元素个数除以表长。装填因子越大，冲突概率越高、性能越差，所以一般要控制在一定阈值以下，超了就扩容 rehash。

还有一个常见的题型是算平均查找长度（ASL），在给定哈希表和冲突解决方式后，求成功查找和失败查找的 ASL。这类题没有捷径，要把每个元素的探测次数老老实实数出来再求平均，做两三道题就熟练了。

排序三剑客：快排、归并、堆排

排序算法里，重点盯这三个，因为它们都做到了平均 O(nlogn) 这一档，但实现思路和特性完全不同。

快速排序的核心是”分治加基准”。随便选一个元素做基准（pivot），把数组重排成”比基准小的都在左、比基准大的都在右”，这一步叫 partition，然后对左右两段递归做同样的事。快排的平均时间复杂度是 O(nlogn)，最坏情况是 O(n²)，最坏发生在数组已经有序、基准每次都选到最值的时候。快排是原地排序，但它不稳定——相等的元素在分区后相对顺序可能改变。记忆关键：快排”先分区后递归”，分区是它的灵魂。

快速排序的 partition 过程

partition 是快排的灵魂，咱们把这一步单独拆开走一遍。这里用最经典的 Lomuto 写法：选数组最右边的元素做 pivot，用一个指针 i 记录”小于等于 pivot 的区域”的右边界，另一个指针 j 从左往右扫，遇到比 pivot 小的就把它换到左边区域里。

具体步骤：

第一步，选 pivot = nums[right]，初始化 i = left - 1（i 表示”小于等于 pivot 区域”目前是空的）。
第二步，j 从 left 扫到 right-1：

如果 nums[j] <= pivot，就把 i 加 1，然后交换 nums[i] 和 nums[j]（把这个小元素塞进左区域）
如果 nums[j] > pivot，啥也不做，j 继续走
第三步，扫完后，把 pivot 放到中间位置：交换 nums[i+1] 和 nums[right]。
第四步，返回 i+1，这就是 pivot 最终所在的下标。此时 pivot 左边都小于等于它，右边都大于它。

代码：

def partition(nums, left, right):
    pivot = nums[right]      # 选最右边做基准
    i = left - 1             # "小于等于 pivot 区域"的右边界
    for j in range(left, right):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]  # 小的换到左边
    nums[i+1], nums[right] = nums[right], nums[i+1]  # pivot 归位
    return i + 1             # 返回 pivot 最终位置

def quickSort(nums, left, right):
    if left < right:
        p = partition(nums, left, right)
        quickSort(nums, left, p - 1)   # 排左半段
        quickSort(nums, p + 1, right)  # 排右半段

输入输出示例。对数组 [5, 2, 8, 3, 9, 1, 7] 做一次 partition（left=0, right=6），pivot = nums[6] = 7：

初始 i = -1
j=0：nums[0]=5 <= 7，i=0，交换 nums[0] 和 nums[0]（自己换自己），数组不变 [5, 2, 8, 3, 9, 1, 7]
j=1：nums[1]=2 <= 7，i=1，交换 nums[1] 和 nums[1]，不变
j=2：nums[2]=8 > 7，跳过
j=3：nums[3]=3 <= 7，i=2，交换 nums[2] 和 nums[3]，数组变成 [5, 2, 3, 8, 9, 1, 7]
j=4：nums[4]=9 > 7，跳过
j=5：nums[5]=1 <= 7，i=3，交换 nums[3] 和 nums[5]，数组变成 [5, 2, 3, 1, 9, 8, 7]
扫完，交换 nums[i+1]=nums[4] 和 nums[right]=nums[6]，也就是交换 9 和 7，数组变成 [5, 2, 3, 1, 7, 8, 9]
返回 i+1 = 4

partition 后，pivot 7 停在下标 4，左边 [5, 2, 3, 1] 都小于等于 7，右边 [8, 9] 都大于 7。然后 quickSort 再对 [5, 2, 3, 1] 和 [8, 9] 分别做同样的 partition，递归下去就排好了。

记住一句话：partition 的核心就是”用 i 划出小于等于区，j 扫一遍把小的塞进去，最后把 pivot 摆到中间”。

归并排序也是分治，但思路相反，是”先递归后合并”。它先把数组一直二分到单个元素，然后两两合并成有序段，合并时利用两个有序段首元素比较来归并。归并的时间复杂度是 O(nlogn)，而且最好、最坏、平均都一样，非常稳定；它也是这三个里唯一的稳定排序；代价是需要 O(n) 的额外空间。对比快排和归并，记一句话：”快排先分后治、归并先治后合；快排原地不稳定、归并稳定费空间”。

堆排序靠的是”堆”这个数据结构。堆是一棵完全二叉树，大顶堆满足父节点大于等于子节点，小顶堆反过来。排序过程是：先把整个数组建成大顶堆，然后把堆顶（最大值）和数组末尾交换，再把剩下的部分重新调整为堆，如此反复，每次取出一个最大值放到末尾。堆排序时间复杂度 O(nlogn)，原地排序，但不稳定。堆的数组表示里有个常用公式：下标从 0 开始时，节点 i 的左孩子是 2i+1、右孩子是 2i+2、父节点是 (i-1)/2，这个一定要记牢，堆排和 TopK 问题都要用。

堆排序建堆：从数组构建大顶堆

堆排序第一步是建堆，这一步经常被一笔带过，其实有讲究。建堆不是”一个一个插入”，那样太慢；正确做法是从最后一个非叶子节点开始，从后往前每个节点做一次”下沉（heapify）”操作。

为什么要从最后一个非叶子节点开始？因为叶子节点没有孩子，本身就满足堆的性质，不用调整。最后一个非叶子节点的下标是 n//2 - 1（n 是数组长度），从这里往前扫到下标 0，每个节点都调用一次 heapify 把它和它的子树调整成大顶堆。

heapify（下沉）操作：对节点 i，比较它和左右孩子，找出三者里最大的那个；如果最大的不是 i，就把 i 和最大的孩子交换，然后对被交换下去的那个位置继续做 heapify（因为它换下来后可能又比它的新孩子小，要继续下沉）。

代码：

def heapify(nums, n, i):
    """把以 i 为根的子树调整成大顶堆，n 是堆的有效大小"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and nums[left] > nums[largest]:
        largest = left
    if right < n and nums[right] > nums[largest]:
        largest = right
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i]
        heapify(nums, n, largest)  # 继续下沉

def buildHeap(nums):
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):  # 从最后一个非叶子节点往前
        heapify(nums, n, i)
    return nums

输入输出示例。对数组 [4, 1, 3, 2] 建大顶堆，n=4，最后一个非叶子节点下标是 4//2-1 = 1：

初始数组 [4, 1, 3, 2]，对应的树是：

i=1（节点 1）：左孩子 nums[3]=2，右孩子没有。2 > 1，最大是 left=3，交换 nums[1] 和 nums[3]，数组变成 [4, 2, 3, 1]。继续对下标 3 做 heapify，但 3 的左孩子 2*3+1=7 超出 n=4，停止。
i=0（节点 4）：左孩子 nums[1]=2，右孩子 nums[2]=3。三者 4、2、3 里 4 最大，largest 还是 0，不交换，停止。

最终建好的大顶堆是 [4, 2, 3, 1]，对应的树是：

每个父节点都大于等于它的孩子，建堆完成。建好堆之后，排序就是反复”把堆顶（最大值）和末尾交换、缩小堆的范围、对新堆顶做 heapify”。比如把 4 换到末尾变成 [1, 2, 3, 4]，对下标 0 做 heapify（堆大小变成 3），3 上浮到堆顶得到 [3, 2, 1, 4]，再把 3 换到下标 2……如此反复直到排好。

建堆的时间复杂度是 O(n)，不是 O(nlogn)，因为越往上的节点越少、下沉距离越短，平均下来是线性的。这个结论是建堆过程的标志性重点，记一下。

这一节的核心重点就三个：稳定性、时间复杂度、空间复杂度。稳定性上记”快排堆排不稳、归并稳”；时间上记”快排最坏 n²、归并堆排都 nlogn 稳如老狗”；空间上记”归并要 O(n) 额外空间，快排堆排原地”。再补一个常见应用：TopK 问题（找前 K 大或前 K 小）用堆做最高效，维护一个大小为 K 的堆即可。

查找：二分与哈希

查找这一块重点两种，对应两种思路。

二分查找要满足一个前提：序列必须有序。它的思路是每次取中间元素和目标比，相等就找到，不等就砍掉一半继续找，时间复杂度 O(logn)。二分查找的坑全在边界上，循环条件是 left<=right 还是 left<right，更新是 left=mid+1 还是 left=mid，取决于你用的是”左闭右闭”还是”左闭右开”区间，选定一种写法就一直用，别来回切。二分还有几个变形很常见：找第一个等于 target 的位置、找最后一个等于 target 的位置、找第一个大于等于 target 的位置，这些变形比基础二分更容易让人混淆。

二分查找：左闭右闭区间完整代码

下面给出最常见的”左闭右闭”写法，顺便讲清楚每个边界为什么这么处理。所谓左闭右闭，就是搜索区间是 [left, right]，left 和 right 都算在区间里。基于这个定义，所有边界处理都有明确含义。

def binarySearch(nums, target):
    left = 0
    right = len(nums) - 1   # 右闭，所以 right 初始化成最后一个下标
    while left <= right:    # 区间里至少还有一个元素就要继续找
        mid = left + (right - left) // 2  # 防止 (left+right) 溢出
        if nums[mid] == target:
            return mid      # 找到，返回下标
        elif nums[mid] < target:
            left = mid + 1   # target 在右半段，mid 已经确认不是答案，排除掉
        else:
            right = mid - 1  # target 在左半段，mid 已经确认不是答案，排除掉
    return -1                # 没找到

边界处理解释：

第一，循环条件为什么是 left <= right 而不是 left < right？因为区间是闭的 [left, right]，当 left == right 时区间里还有一个元素 nums[left] 没查过，必须再进一轮循环查它。如果用 left < right，就会漏掉最后一个元素。

第二，更新时为什么是 left = mid + 1 和 right = mid - 1，而不是 left = mid？因为 nums[mid] 已经确认不等于 target（否则上一行就 return 了），所以 mid 这个位置可以安全排除掉，下一次搜索区间是 [mid+1, right] 或 [left, mid-1]。如果写成 left = mid，在 left 和 right 相邻时就可能死循环（mid 取整后还是 left）。

第三，mid 的计算用 left + (right - left) // 2 而不是 (left + right) // 2，是为了防止 left+right 在某些语言里溢出（Python 不会溢出，但这是通用写法，养成习惯）。

输入输出示例。在有序数组 [1, 3, 5, 7, 9, 11, 13] 里找 target = 7：

left=0, right=6, mid=3, nums[3]=7 == 7，返回 3

找 target = 4（不在数组里）：

left=0, right=6, mid=3, nums[3]=7 > 4, right=2
left=0, right=2, mid=1, nums[1]=3 < 4, left=2
left=2, right=2, mid=2, nums[2]=5 > 4, right=1
left=2, right=1, left > right，退出循环，返回 -1

哈希查找前面哈希表那节已经讲过，平均 O(1)，优势是无序也能查，劣势是冲突会影响性能、且不支持范围查询和有序遍历。两者对比：有序且查找频繁用二分，等值查找为主、不要求有序用哈希。

图遍历：BFS与DFS

图的两种遍历方式必须分清，它们用的辅助结构不同、应用场景也不同。

BFS 是广度优先搜索，思路是从起点出发，一层一层地往外扩，像往水里丢石子泛起的水波纹。它靠队列实现：起点入队，每次出队一个顶点，把它所有未访问的邻居入队，循环到队空。BFS 的特点是”层层推进”，所以它能用来求无权图的最短路径，也能做二叉树的层序遍历。

DFS 是深度优先搜索，思路是从起点出发，一条路走到底走不动了再回退换路，像走迷宫一直贴着墙走到死胡同才回头。它靠递归（本质是栈）或显式栈实现。DFS 适合连通性判断、拓扑排序、找所有解、环检测这类问题。

两者对比记忆：BFS 用队列、DFS 用栈或递归；BFS 找最短路径、DFS 找所有路径或判断连通。时间复杂度上，用邻接表存储时都是 O(V+E)（V 是顶点数、E 是边数），用邻接矩阵时是 O(V²)。这个复杂度对比是重点知识。

图的 BFS 和 DFS：用一个具体的图走一遍

光说”一层层扩””走到底再回退”还是抽象，咱们拿一个具体的无向图实际遍历一次。图长这样：

边有这些：1-2、1-3、2-4、2-5、3-6、4-7、5-7。这是个无向图，每条边双向都通。用邻接表表示（每个顶点的邻居按编号从小到大排）：

1 的邻居：2, 3
2 的邻居：1, 4, 5
3 的邻居：1, 6
4 的邻居：2, 7
5 的邻居：2, 7
6 的邻居：3
7 的邻居：4, 5

先做 BFS，从顶点 1 开始，用队列，每次出队一个顶点就把它的未访问邻居入队：

起点入队，队列=[1]，已访问={1}，输出=[]
出队 1，输出=[1]，邻居 [2, 3] 都没访问，入队。队列=[2, 3]，已访问={1,2,3}
出队 2，输出=[1, 2]，邻居 [1, 4, 5]，1 已访问，4 和 5 入队。队列=[3, 4, 5]，已访问={1,2,3,4,5}
出队 3，输出=[1, 2, 3]，邻居 [1, 6]，1 已访问，6 入队。队列=[4, 5, 6]，已访问+={6}
出队 4，输出=[1, 2, 3, 4]，邻居 [2, 7]，2 已访问，7 入队。队列=[5, 6, 7]，已访问+={7}
出队 5，输出=[1, 2, 3, 4, 5]，邻居 [2, 7] 都已访问，不入队。队列=[6, 7]
出队 6，输出=[1, 2, 3, 4, 5, 6]，邻居 [3] 已访问。队列=[7]
出队 7，输出=[1, 2, 3, 4, 5, 6, 7]，邻居 [4, 5] 都已访问。队列=[]
队空，结束。BFS 结果：1, 2, 3, 4, 5, 6, 7

你看 BFS 的特点是按距离起点 1 的层数访问：第 0 层是 1，第 1 层是 2 和 3，第 2 层是 4、5、6，第 3 层是 7。这就是”层层推进”。

再做 DFS，从顶点 1 开始，用递归（每个顶点访问后立刻递归访问它第一个未访问的邻居）：

访问 1，输出=[1]，邻居 [2, 3]，先递归 2
访问 2，输出=[1, 2]，邻居 [1, 4, 5]，1 已访问，递归 4
访问 4，输出=[1, 2, 4]，邻居 [2, 7]，2 已访问，递归 7
访问 7，输出=[1, 2, 4, 7]，邻居 [4, 5]，4 已访问，递归 5
访问 5，输出=[1, 2, 4, 7, 5]，邻居 [2, 7] 都已访问，回溯
回到 7，邻居都访问完，回溯
回到 4，邻居都访问完，回溯
回到 2，邻居都访问完，回溯
回到 1，邻居 [2, 3] 里 2 已访问，递归 3
访问 3，输出=[1, 2, 4, 7, 5, 3]，邻居 [1, 6]，1 已访问，递归 6
访问 6，输出=[1, 2, 4, 7, 5, 3, 6]，邻居 [3] 已访问，回溯
回到 3，回溯
回到 1，邻居都访问完，结束

DFS 结果：1, 2, 4, 7, 5, 3, 6。可以看到 DFS 是”一条路走到黑再回头”，先把 1->2->4->7->5 这一条路走到底，再回头走 3->6 这一支。

代码对照着看：

from collections import deque, defaultdict

# 构造图
graph = defaultdict(list)
edges = [(1,2), (1,3), (2,4), (2,5), (3,6), (4,7), (5,7)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
# 邻居排序，保证访问顺序确定
for v in graph:
    graph[v].sort()

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

def dfs(graph, start):
    visited = set()
    result = []
    def _dfs(node):
        visited.add(node)
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                _dfs(neighbor)
    _dfs(start)
    return result

print(bfs(graph, 1))  # [1, 2, 3, 4, 5, 6, 7]
print(dfs(graph, 1))  # [1, 2, 4, 7, 5, 3, 6]

注意 BFS 要在入队时立刻标记 visited（防止同一个顶点被重复入队），DFS 在递归入口标记 visited。这是个容易写错的地方，记住”入队即标记”。

动态规划与贪心：看似像实则不同

这两个算法长得像，都涉及”做选择”，但内核完全不同，是最喜欢拿来对比的一对。

动态规划（DP）的核心思想是把大问题拆成子问题，当子问题有重叠时，把每个子问题的结果记下来避免重复计算。能用 DP 的问题必须满足两个性质：最优子结构（大问题的最优解由子问题的最优解构成）和重叠子问题。做题的关键是写出状态转移方程，也就是”当前状态怎么从前面的状态推过来”。经典例子有斐波那契数列、背包问题（01 背包和完全背包）、最长公共子序列、最长上升子序列、编辑距离。DP 一般是自底向上递推，能保证全局最优，代价是时间和空间都不小（空间往往可以用”滚动数组”优化）。

贪心算法的思路是每一步都选”当前看起来最好”的选项，不回头、不后悔。它不保证全局最优，只有在问题具有”贪心选择性质”时才是正确的。典型例子有活动选择问题（按结束时间排序选最多不冲突活动）、Huffman 编码、最小生成树的 Prim 和 Kruskal 算法、部分背包问题（可分割的背包）。贪心一般效率高、实现简单，但适用面窄。

两者的根本区别要记牢：DP 是”全局考虑、自底向上、保证最优但慢”；贪心是”局部选择、不回头、快但不一定最优”。判断一道题该用哪个，可以先想”贪心能不能成立”——如果每一步的局部最优确实能推出全局最优，就用贪心；如果不行、需要枚举所有子问题的组合，就用 DP。一个简单的判别信号：背包问题里，物品可分割（部分背包）用贪心，物品不可分割（01 背包）用 DP，这个对比非常典型。

动态规划状态转移方程：斐波那契和 01 背包

状态转移方程是 DP 的灵魂，说白了就是”当前状态怎么从前面的状态推过来”。咱们用两个最经典的例子把它写明白。

第一个例子，斐波那契数列。斐波那契数列的定义是：第 0 项是 0，第 1 项是 1，从第 2 项开始每一项等于前两项之和。这就是天然的”当前状态由前面状态推过来”。

状态定义：dp[i] 表示第 i 个斐波那契数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
边界条件：dp[0] = 0，dp[1] = 1
计算顺序：从 i=2 递推到 i=n

代码：

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]   # 状态转移方程
    return dp[n]

输入 n=10，输出 55。验算一下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55，第 10 项确实是 55。

这里”重叠子问题”特别明显：算 fib(5) 要用 fib(4) 和 fib(3)，算 fib(4) 又要用 fib(3) 和 fib(2)，fib(3) 被算了两次。朴素递归会重复算很多次，DP 把每个 fib(i) 算一次存起来，这就是 DP 的价值。

第二个例子，01 背包问题。有 n 个物品，每件有重量 w[i] 和价值 v[i]，背包容量是 W，每件物品要么装要么不装（不能分割），求能装出的最大价值。

状态定义：dp[i][j] 表示”前 i 件物品、背包容量为 j 时能装的最大价值”
状态转移方程（对第 i 件物品，i 从 1 开始数）：
- 不装第 i 件：dp[i][j] = dp[i-1][j]
- 装第 i 件（前提是 j >= w[i-1]，能装得下）：dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
- 取两者较大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
边界条件：dp[0][j] = 0（没有物品可装，价值为 0）
计算顺序：i 从 1 到 n，j 从 0 到 W

注意下标对应：代码里物品编号从 0 开始，所以第 i 件物品（i 从 1 数）的重量是 w[i-1]、价值是 v[i-1]。

代码：

def knapsack01(w, v, W):
    n = len(w)
    # dp[i][j]：前 i 件物品、容量 j 时的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i-1][j]  # 不装第 i 件
            if j >= w[i-1]:        # 能装得下才考虑装
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])
    return dp[n][W]

输入示例：w = [2, 3, 4, 5]，v = [3, 4, 5, 6]，W = 5。也就是四件物品，重量分别是 2、3、4、5，价值分别是 3、4、5、6，背包容量 5。

走一遍：容量 5 能装的组合有”装第 1 件和第 2 件”（重量 2+3=5，价值 3+4=7）、”装第 3 件”（重量 4，价值 5）、”装第 4 件”（重量 5，价值 6）。最大价值是 7。

代码跑出来 dp[4][5] = 7，结果对得上。这个状态转移方程的核心是”每件物品面临装或不装两个选择”，所以叫 01 背包（0 不装、1 装）。如果是完全背包（每件物品可以装无限件），状态转移方程会变成 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1])，注意第二个是 dp[i] 不是 dp[i-1]，因为同一件物品可以重复装。

数据结构与算法知识速记

数组和链表的取舍不要记反：数组查得快 O(1)、增删慢 O(n)；链表查得慢 O(n)、增删快 O(1)。栈是 LIFO、队列是 FIFO，循环队列判空用 front==rear、判满牺牲一个单元用 (rear+1)%size==front，这三个公式别张冠李戴。满二叉树和完全二叉树一字之差，”满”要求所有层都满，”完全”允许最后一层不满但必须从左连续。二叉树遍历里，前序加中序、后序加中序都能唯一确定一棵树，但前序加后序不行。B 树矮胖是为了减少磁盘 IO，红黑树最长路径不超过最短路径两倍，五条性质里”红节点的孩子必黑”和”黑高相同”最需要记牢。AVL 比 Red-Black 更严格平衡，查多用 AVL、增删多用 Red-Black。

图的存储上，稠密图用邻接矩阵、稀疏图用邻接表，无向图邻接矩阵对称。哈希表冲突处理两大流派，开放定址法有聚集问题、拉链法多存指针，装填因子越大性能越差。排序稳定性口诀”快排堆排不稳、归并稳”，快排最坏 n²、归并和堆排三种复杂度都是 nlogn，归并要 O(n) 额外空间。二分查找的坑在区间边界，选定左闭右闭或左闭右开就别再切。图遍历中 BFS 配队列、DFS 配栈或递归，邻接表下两者都是 O(V+E)。最后，DP 和贪心的判别：能证明”局部最优推全局最优”用贪心，否则老老实实写状态转移方程用 DP，01 背包用 DP、部分背包用贪心，这个对比例子记牢就能挡住大半混淆点。

第一章 数据结构与算法：把数据摆明白，把套路用清楚

线性表：数组与链表的取舍

链表逆置：三指针法

快慢指针找中点

快慢指针判断是否有环

栈与队列：一个后进先出，一个先进先出

树：从二叉树到红黑树

二叉树四种遍历：用一棵具体的树走一遍

图：邻接矩阵与邻接表

哈希表：用空间换时间的典范

哈希表冲突处理：线性探测和拉链法的具体操作

排序三剑客：快排、归并、堆排

快速排序的 partition 过程

堆排序建堆：从数组构建大顶堆

查找：二分与哈希

二分查找：左闭右闭区间完整代码

图遍历：BFS与DFS

图的 BFS 和 DFS：用一个具体的图走一遍

动态规划与贪心：看似像实则不同

动态规划状态转移方程：斐波那契和 01 背包

数据结构与算法知识速记

第一章数据结构与算法：把数据摆明白，把套路用清楚