数据结构与算法¶
0. 要点汇总¶
本篇文章的要点整理如下
数据结构：计算机存储、组织数据的方式，是高效访问和修改数据的基础
算法：解决特定问题的一系列明确指令，具有输入、输出、有穷性、确定性和可行性
抽象数据类型(ADT)：数据结构的逻辑定义，与具体实现分离
时间复杂度：算法执行时间与输入规模的关系，常用大O表示法描述
空间复杂度：算法执行过程中所需存储空间与输入规模的关系
渐近记号：大O、大Ω、大Θ，用于描述算法复杂度的上界、下界和紧确界
数组：连续存储的元素集合，支持随机访问，插入删除效率低
链表：通过指针连接的节点序列，插入删除效率高，访问效率低
栈：后进先出(LIFO)的数据结构
队列：先进先出(FIFO)的数据结构
树：层次化的非线性数据结构，包括二叉树、搜索树、平衡树等
图：由顶点和边组成的数据结构，表示复杂关系网络
哈希表：通过哈希函数实现快速查找的数据结构
排序算法：将数据按特定顺序排列的算法，如冒泡、插入、快速、归并等
查找算法：在数据集中查找特定元素的算法，如顺序查找、二分查找等
分治法：将问题分解为子问题递归求解的算法设计策略
贪心算法：每步选择局部最优解以期达到全局最优的算法设计策略
动态规划：通过存储子问题解避免重复计算的算法设计策略
回溯法：通过系统地搜索解空间找到所有解的算法设计策略
分支限界法：在回溯法基础上引入限界函数优化搜索的算法设计策略
1. 数据结构基础¶
1.1 基本概念¶
数据与数据结构
数据是对客观事物的符号表示。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
逻辑结构与物理结构
- 逻辑结构：数据元素之间的逻辑关系，与计算机无关
线性结构：一对一关系
树形结构：一对多关系
图状结构：多对多关系
- 物理结构：数据在计算机中的存储方式
顺序存储：连续存储
链式存储：非连续存储
抽象数据类型(ADT)
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
- ADT的特点：
数据抽象：隐藏数据表示细节
操作封装：通过操作访问和修改数据
算法的五个特征
有穷性：算法在有限步骤后终止
确定性：每步指令含义明确
输入：有零个或多个输入
输出：有一个或多个输出
可行性：每步操作都可以在有限时间内完成
1.2 算法复杂度分析¶
时间复杂度
时间复杂度是算法执行时间随输入规模增长的渐近增长率。
大O记号
f(n) = O(g(n))表示存在正常数c和n₀，使得当n ≥ n₀时，|f(n)| ≤ c|g(n)|
- 常见时间复杂度（按效率从高到低）：
O(1)：常数时间
O(log n)：对数时间
O(n)：线性时间
O(n log n)：线性对数时间
O(n²)：平方时间
O(n³)：立方时间
O(2ⁿ)：指数时间
O(n!)：阶乘时间
空间复杂度
空间复杂度是算法所需存储空间随输入规模增长的渐近增长率。
复杂度分析示例
# 时间复杂度O(n)，空间复杂度O(1)
def sum_array(arr):
total = 0
for x in arr:
total += x
return total
# 时间复杂度O(n²)，空间复杂度O(1)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
最优、最坏、平均情况
最优情况：算法执行的最快情况 最坏情况：算法执行的最慢情况 平均情况：算法执行的平均情况（需要概率分布）
通常我们关注最坏情况的时间复杂度。
1.3 渐近记号¶
大O记号（上界）
f(n) = O(g(n))表示f(n)的增长速度不超过g(n)
大Ω记号（下界）
f(n) = Ω(g(n))表示f(n)的增长速度不低于g(n)
大Θ记号（紧确界）
f(n) = Θ(g(n))表示f(n)的增长速度与g(n)相同
小o记号
f(n) = o(g(n))表示f(n)的增长速度严格小于g(n)
小ω记号
f(n) = ω(g(n))表示f(n)的增长速度严格大于g(n)
渐近记号的性质
传递性：若f(n) = O(g(n))且g(n) = O(h(n))，则f(n) = O(h(n))
反射性：f(n) = O(f(n))
对称性：f(n) = Θ(g(n))当且仅当g(n) = Θ(f(n))
移位性：若f(n) = O(g(n))，则f(n)/k = O(g(n)/k)
2. 线性数据结构¶
2.1 数组¶
数组的定义
数组是存储在连续内存空间中的相同类型元素的集合。
数组的特性
随机访问：通过下标直接访问元素，时间复杂度O(1)
连续存储：元素在内存中连续排列
固定大小：数组创建后大小固定（某些语言支持动态数组）
类型相同：所有元素类型相同
基本操作
访问：O(1)
搜索：O(n)
插入：O(n)（需要移动元素）
删除：O(n)（需要移动元素）
多维数组
二维数组：矩阵，用于存储表格数据 三维数组：立方体，用于存储立体数据
数组的应用
矩阵运算
图的邻接矩阵表示
动态规划
动态数组
- 支持动态扩容的数组实现，如：
C++的std::vector
Java的ArrayList
Python的list
扩容策略：通常按2倍扩容，均摊时间复杂度O(1)
2.2 链表¶
链表的定义
链表是由节点组成的线性序列，每个节点包含数据和指向下一个节点的指针。
链表的类型
单链表：每个节点只有一个指向后继的指针
双向链表：每个节点有两个指针，分别指向前驱和后继
循环链表：尾节点的指针指向头节点
双向循环链表：结合双向链表和循环链表的特点
链表的特性
非连续存储：节点可以在内存中任意位置
动态大小：可以动态添加或删除节点
插入删除效率高：在已知位置插入或删除只需O(1)时间
访问效率低：需要从头开始遍历，访问第k个元素需要O(k)时间
基本操作
头插/头删：O(1)
尾插/尾删：O(1)（对于双向链表）或O(n)（对于单链表）
按位置插入/删除：O(k)（k是位置）
搜索：O(n)
链表的应用
实现栈和队列
实现图的邻接表表示
内存管理
链表 vs 数组
特性 |
数组 |
链表 |
|---|---|---|
访问 |
O(1) |
O(n) |
插入/删除 |
O(n) |
O(1)（已知位置） |
内存连续 |
是 |
否 |
空间开销 |
小 |
大（需要指针） |
2.3 栈¶
栈的定义
栈是一种后进先出(LIFO)的线性数据结构。
栈的基本操作
push(x)：将元素x压入栈顶
pop()：弹出栈顶元素
top()：返回栈顶元素
isEmpty()：判断栈是否为空
size()：返回栈中元素个数
栈的实现
数组实现:
class ArrayStack:
def __init__(self):
self.data = []
def push(self, x):
self.data.append(x)
def pop(self):
return self.data.pop()
def top(self):
return self.data[-1]
链表实现:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedListStack:
def __init__(self):
self.top = None
def push(self, x):
node = Node(x)
node.next = self.top
self.top = node
def pop(self):
if self.top is None:
raise Exception("Stack is empty")
val = self.top.val
self.top = self.top.next
return val
栈的应用
函数调用栈
表达式求值
括号匹配
撤销操作
浏览器历史记录
2.4 队列¶
队列的定义
队列是一种先进先出(FIFO)的线性数据结构。
队列的基本操作
enqueue(x)：将元素x加入队尾
dequeue()：从队头取出元素
front()：返回队头元素
isEmpty()：判断队列是否为空
size()：返回队列中元素个数
队列的类型
普通队列：标准的FIFO队列
循环队列：通过模运算实现，避免假溢出
优先队列：元素按优先级出队
双端队列：两端都可以插入和删除
队列的实现
数组实现（循环队列）:
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.data = [None] * capacity
self.front = 0
self.rear = 0
self.size = 0
def enqueue(self, x):
if self.size == self.capacity:
raise Exception("Queue is full")
self.data[self.rear] = x
self.rear = (self.rear + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.size == 0:
raise Exception("Queue is empty")
val = self.data[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return val
链表实现:
class LinkedListQueue:
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def enqueue(self, x):
node = Node(x)
if self.rear is None:
self.front = self.rear = node
else:
self.rear.next = node
self.rear = node
self.size += 1
def dequeue(self):
if self.front is None:
raise Exception("Queue is empty")
val = self.front.val
self.front = self.front.next
if self.front is None:
self.rear = None
self.size -= 1
return val
队列的应用
操作系统的任务调度
打印机任务队列
广度优先搜索(BFS)
缓冲区
消息队列
3. 树形数据结构¶
3.1 树的基本概念¶
树的定义
树是由n(n ≥ 0)个节点组成的有限集合。
树的基本术语
根节点：树的最顶层节点
叶子节点：没有子节点的节点
内部节点：非叶子节点
父节点：直接前驱节点
子节点：直接后继节点
兄弟节点：同一父节点的子节点
路径：从一个节点到另一个节点的节点序列
路径长度：路径上边的数量
深度：根节点到某节点的路径长度
高度：某节点到最远叶子节点的最长路径长度
度：节点的子节点个数
树的度：树中节点的最大度数
树的表示方法
双亲表示法：每个节点存储其父节点的下标
孩子表示法：每个节点存储其所有孩子节点
孩子兄弟表示法：每个节点存储其第一个孩子和右兄弟
3.2 二叉树¶
二叉树的定义
二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树。
二叉树的性质
第i层最多有2^(i-1)个节点
深度为k的二叉树最多有2^k - 1个节点
对于任意二叉树，叶子节点数n₀ = 度为2的节点数n₂ + 1
二叉树的类型
满二叉树：除最后一层外，每层节点数都达到最大，最后一层节点全部靠左
完全二叉树：除最后一层外，每层节点数都达到最大，最后一层节点从左到右填充
平衡二叉树：任意节点的左右子树高度差不超过1
二叉搜索树(BST)：左子树所有节点值 < 根节点值 < 右子树所有节点值
二叉树的遍历
前序遍历：根 - 左 - 右
中序遍历：左 - 根 - 右
后序遍历：左 - 右 - 根
层序遍历：按层从上到下，从左到右
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def preorder(root):
if root is None:
return
print(root.val)
preorder(root.left)
preorder(root.right)
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.val)
inorder(root.right)
def postorder(root):
if root is None:
return
postorder(root.left)
postorder(root.right)
print(root.val)
def level_order(root):
if root is None:
return []
queue = [root]
result = []
while queue:
node = queue.pop(0)
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
二叉树的应用
哈夫曼编码
表达式树
决策树
堆
3.3 二叉搜索树¶
二叉搜索树的定义
- 二叉搜索树(BST)是一种特殊的二叉树，满足：
左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
左右子树本身也是BST
BST的操作
查找：O(h)，h是树的高度
def search(root, val):
if root is None or root.val == val:
return root
if val < root.val:
return search(root.left, val)
else:
return search(root.right, val)
插入：O(h)
def insert(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
return root
删除：O(h)
def delete(root, val):
if root is None:
return root
if val < root.val:
root.left = delete(root.left, val)
elif val > root.val:
root.right = delete(root.right, val)
else:
# 节点有一个子节点或无子节点
if root.left is None:
return root.right
elif root.right is None:
return root.left
# 节点有两个子节点
temp = min_value_node(root.right)
root.val = temp.val
root.right = delete(root.right, temp.val)
return root
BST的效率
最优情况（平衡）：O(log n) 最坏情况（退化成链表）：O(n)
3.4 平衡二叉树¶
平衡二叉树的定义
平衡二叉树是一种自平衡的二叉搜索树，保证树的高度始终为O(log n)。
AVL树
- AVL树是最早提出的平衡二叉树，满足：
任意节点的左右子树高度差（平衡因子）的绝对值不超过1
每次插入或删除后，通过旋转恢复平衡
- 旋转操作：
左旋
右旋
左右旋
右左旋
红黑树
- 红黑树是一种高效的自平衡二叉搜索树，满足：
每个节点是红色或黑色
根节点是黑色
所有叶子节点是黑色
红色节点的两个子节点都是黑色
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
红黑树通过颜色标记和旋转操作保证平衡。
平衡二叉树的应用
C++的std::map和std::set
Java的TreeMap和TreeSet
Linux内核的调度器
3.5 堆¶
堆的定义
- 堆是一种特殊的完全二叉树，满足：
大顶堆：每个节点的值 >= 其子节点的值
小顶堆：每个节点的值 <= 其子节点的值
堆的性质
堆总是一棵完全二叉树
堆中某个节点的值总是不大于或不小于其父节点的值
堆的操作
插入：O(log n)
def insert(heap, val):
heap.append(val)
sift_up(heap, len(heap) - 1)
def sift_up(heap, i):
parent = (i - 1) // 2
if i > 0 and heap[i] > heap[parent]:
heap[i], heap[parent] = heap[parent], heap[i]
sift_up(heap, parent)
删除堆顶：O(log n)
def extract_max(heap):
if len(heap) == 0:
raise Exception("Heap is empty")
max_val = heap[0]
heap[0] = heap[-1]
heap.pop()
sift_down(heap, 0)
return max_val
def sift_down(heap, i):
n = len(heap)
while True:
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < n and heap[left] > heap[largest]:
largest = left
if right < n and heap[right] > heap[largest]:
largest = right
if largest == i:
break
heap[i], heap[largest] = heap[largest], heap[i]
i = largest
建堆：O(n)
堆的应用
堆排序
优先队列
求Top K问题
合并K个有序链表
4. 图数据结构¶
4.1 图的基本概念¶
图的定义
图是由顶点集合V和边集合E组成的数据结构，记为G = (V, E)。
图的基本术语
顶点(Vertex)：图中的节点
边(Edge)：连接顶点的线
无向图：边没有方向的图
有向图：边有方向的图
加权图：边有权重的图
度(Degree)：与顶点相连的边的数量
入度(Indegree)：指向顶点的边的数量
出度(Outdegree)：从顶点指出的边的数量
路径：从一个顶点到另一个顶点的顶点序列
环：起点和终点相同的路径
连通图：任意两个顶点之间都有路径的图
完全图：每对顶点之间都有边的图
图的表示方法
邻接矩阵：
# 无向图的邻接矩阵
adj_matrix = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 0],
[0, 1, 0, 0]
]
- 优点：
判断两个顶点是否相邻：O(1)
适合稠密图
- 缺点：
空间复杂度：O(V²)
遍历所有邻接顶点：O(V)
邻接表：
# 无向图的邻接表
adj_list = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1],
3: [1]
}
- 优点：
空间复杂度：O(V + E)
遍历所有邻接顶点：O(degree)
- 缺点：
判断两个顶点是否相邻：O(degree)
4.2 图的遍历¶
深度优先搜索(DFS)
DFS从起始顶点开始，尽可能深地搜索图的分支。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
时间复杂度：O(V + E) 空间复杂度：O(V)
广度优先搜索(BFS)
BFS从起始顶点开始，逐层向外扩展。
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
vertex = queue.popleft()
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
时间复杂度：O(V + E) 空间复杂度：O(V)
4.3 最短路径算法¶
Dijkstra算法
Dijkstra算法用于求单源最短路径，适用于非负权重的有向图。
import heapq
def def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
时间复杂度：O((V + E)log V) 空间复杂度：O(V)
Floyd-Warshall算法
Floyd-Warshall算法用于求所有顶点对之间的最短路径。
def floyd_warshall(graph):
n = len(graph)
dist = [[graph[i][j] for j in range(n)] for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
时间复杂度：O(V³) 空间复杂度：O(V²)
4.4 最小生成树¶
最小生成树的定义
最小生成树是连通图的生成树中，边权之和最小的树。
Prim算法
Prim算法从任意顶点开始，逐步扩展生成树。
def prim(graph):
n = len(graph)
mst = []
visited = set()
# 初始化距离
min_edge = [(float('infinity'), None, i) for i in range(n)]
min_edge[0] = (0, None, 0)
while len(visited) < n:
# 找到最小边
weight, _, u = min((min_edge[i] for i in range(n) if i not in visited), key=lambda x: x[0])
visited.add(u)
if weight != float('infinity'):
mst.append((u, weight))
# 更新邻接点的距离
for v, w in graph[u].items():
if v not in visited and w < min_edge[v][0]:
min_edge[v] = (w, u, v)
return mst
时间复杂度：O(V²)（使用优先队列可优化为O((V + E)log V)）
Kruskal算法
Kruskal算法按边的权重从小到大排序，逐步选择边。
def kruskal(graph):
edges = []
for u in graph:
for v, weight in graph[u].items():
edges.append((weight, u, v))
edges.sort()
parent = {v: v for v in graph}
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
def union(v1, v2):
root1 = find(v1)
root2 = find(v2)
if root1 != root2:
parent[root1] = root2
mst = []
for weight, u, v in edges:
if find(u) != find(v):
union(u, v)
mst.append((u, v, weight))
return mst
时间复杂度：O(E log E)
5. 哈希表¶
5.1 哈希函数¶
哈希函数的定义
哈希函数将任意长度的输入映射到固定长度的输出。
好的哈希函数的性质
确定性：相同输入产生相同输出
高效性：计算快速
均匀性：输出分布均匀
雪崩效应：输入的微小变化导致输出的巨大变化
常见的哈希函数
除法哈希：
其中m是哈希表的大小，通常选择素数。
乘法哈希：
其中A = (√5 - 1)/2 ≈ 0.618
MurmurHash：非加密型哈希函数，速度快，分布均匀
SHA：安全哈希算法，用于加密和完整性校验
5.2 哈希冲突解决¶
哈希冲突的定义
不同的键映射到相同的哈希值。
冲突解决方法
1. 开放寻址法： 当冲突发生时，寻找下一个可用的位置。
线性探测：h(k, i) = (h’(k) + i) mod m
二次探测：h(k, i) = (h’(k) + c₁i + c₂i²) mod m
双重哈希：h(k, i) = (h₁(k) + i·h₂(k)) mod m
2. 链地址法： 每个哈希桶维护一个链表，冲突的元素添加到链表中。
3. 再哈希法： 使用多个哈希函数，当冲突时尝试下一个哈希函数。
装载因子
装载因子 = 元素个数 / 哈希表大小
当装载因子超过阈值时，需要扩容（通常扩容为原来的2倍）。
5.3 哈希表的操作¶
基本操作
插入：平均O(1)，最坏O(n)
查找：平均O(1)，最坏O(n)
删除：平均O(1)，最坏O(n)
class HashTable:
def __init__(self, size=16):
self.size = size
self.count = 0
self.table = [[] for _ in range(size)]
def hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
self.count += 1
if self.count / self.size > 0.7:
self.resize()
def get(self, key):
index = self.hash(key)
for k, v in self.table[index]:
if k == key:
return v
raise KeyError(key)
def remove(self, key):
index = self.hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index].pop(i)
self.count -= 1
return
raise KeyError(key)
def resize(self):
old_table = self.table
self.size *= 2
self.count = 0
self.table = [[] for _ in range(self.size)]
for bucket in old_table:
for key, value in bucket:
self.insert(key, value)
哈希表的应用
缓存
符号表
数据库索引
去重
6. 排序算法¶
6.1 基本排序算法¶
冒泡排序
重复遍历数组，比较相邻元素并交换位置。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
时间复杂度：O(n²) 空间复杂度：O(1) 稳定性：稳定
插入排序
将元素逐个插入到已排序序列的适当位置。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
时间复杂度：O(n²) 空间复杂度：O(1) 稳定性：稳定
选择排序
每次选择最小元素放到已排序序列末尾。
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
时间复杂度：O(n²) 空间复杂度：O(1) 稳定性：不稳定
6.2 高级排序算法¶
快速排序
选择基准元素，将数组分为两部分，递归排序。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
时间复杂度：平均O(n log n)，最坏O(n²) 空间复杂度：O(log n) 稳定性：不稳定
归并排序
分治法，将数组分成两半，分别排序后合并。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
时间复杂度：O(n log n) 空间复杂度：O(n) 稳定性：稳定
堆排序
利用堆数据结构进行排序。
def heap_sort(arr):
n = len(arr)
# 建堆
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)
# 排序
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
sift_down(arr, i, 0)
return arr
def sift_down(arr, n, i):
while True:
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest == i:
break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
时间复杂度：O(n log n) 空间复杂度：O(1) 稳定性：不稳定
6.3 特殊排序算法¶
计数排序
适用于范围有限的整数排序:
def counting_sort(arr):
max_val = max(arr)
min_val = min(arr)
range_val = max_val - min_val + 1
count = [0] * range_val
for num in arr:
count[num - min_val] += 1
result = []
for i in range(range_val):
result.extend([i + min_val] * count[i])
return result
时间复杂度：O(n + k)，k是数值范围 空间复杂度：O(k)
桶排序
将元素分配到不同的桶中，每个桶单独排序。
def bucket_sort(arr, bucket_size=5):
if len(arr) == 0:
return arr
min_val, max_val = min(arr), max(arr)
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for num in arr:
buckets[(num - min_val) // bucket_size].append(num)
result = []
for bucket in buckets:
result.extend(insertion_sort(bucket))
return result
时间复杂度：平均O(n + k)，最坏O(n²) 空间复杂度：O(n + k)
基数排序
按数位从低位到高位排序。
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for num in arr:
index = (num // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
for i in range(n):
arr[i] = output[i]
时间复杂度：O(d·n)，d是最大数字的位数 空间复杂度：O(n + k)
7. 查找算法¶
7.1 顺序查找¶
顺序查找
从头到尾遍历数组，直到找到目标元素或遍历完整个数组。
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
时间复杂度：O(n) 空间复杂度：O(1)
7.2 二分查找¶
二分查找
在有序数组中查找元素，每次将搜索范围缩小一半。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
时间复杂度：O(log n) 空间复杂度：O(1)
条件
数组必须有序。
7.3 插值查找¶
插值查找
在均匀分布的有序数组中，插值查找比二分查找更高效。
def interpolation_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right and target >= arr[left] and target <= arr[right]:
if left == right:
if arr[left] == target:
return left
return -1
pos = left + ((target - arr[left]) * (right - left)) // (arr[right] - arr[left])
if arr[pos] == target:
return pos
elif arr[pos] < target:
left = pos + 1
else:
right = pos - 1
return -1
时间复杂度：平均O(log log n)，最坏O(n) 空间复杂度：O(1)
条件
数组必须有序且均匀分布。
7.4 哈希查找¶
哈希查找
通过哈希函数快速定位元素。
def hash_search(hash_table, key):
index = hash(key) % len(hash_table)
for k, v in hash_table[index]:
if k == key:
return v
return None
时间复杂度：平均O(1)，最坏O(n) 空间复杂度：O(n)
8. 算法设计策略¶
8.1 分治法¶
分治法的思想
将问题分解为更小的子问题，递归求解子问题，然后合并子问题的解。
分治法的步骤
分解：将问题分解为更小的子问题
解决：递归求解子问题
合并：合并子问题的解
典型应用
归并排序
快速排序
二分查找
大整数乘法
矩阵乘法
大整数乘法（Karatsuba算法）
将n位数分解为两个n/2位数。
- 只计算3次乘法：
Z₁ = A·C
Z₂ = (A - B)(D - C)
Z₃ = B·D
时间复杂度：O(n^(log₂3)) ≈ O(n^1.585)
8.2 贪心算法¶
贪心算法的思想
每步选择局部最优解，期望得到全局最优解。
贪心算法的性质
贪心选择性质：每一步的贪心选择最终能得到全局最优解
最优子结构：问题的最优解包含其子问题的最优解
典型应用
活动选择问题
霍夫曼编码
最小生成树（Prim、Kruskal算法）
最短路径（Dijkstra算法）
活动选择问题
给定n个活动，每个活动有开始时间和结束时间，选择尽可能多的不冲突活动:
.. code-block:: python
- def activity_selection(activities):
activities.sort(key=lambda x: x[1]) # 按结束时间排序 selected = [] prev_end = float(‘-inf’)
- for start, end in activities:
- if start >= prev_end:
selected.append((start, end)) prev_end = end
return selected
时间复杂度：O(n log n)
8.3 动态规划¶
动态规划的思想
将问题分解为重叠子问题，存储子问题的解避免重复计算。
动态规划的步骤
定义子问题
建立状态转移方程
确定初始条件和边界条件
计算最优解
斐波那契数列
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
时间复杂度：O(n) 空间复杂度：O(n)（可优化为O(1)）
背包问题
0-1背包问题：给定n个物品，每个物品有重量和价值，背包容量为W，选择物品使总价值最大:
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
时间复杂度：O(nW) 空间复杂度：O(nW)
8.4 回溯法¶
回溯法的思想
通过系统地搜索解空间找到所有解，当搜索不满足条件时回溯到上一步。
回溯法的步骤
定义解空间
选择搜索路径
判断是否满足条件
回溯或继续搜索
典型应用
N皇后问题
排列组合
子集问题
数独
N皇后问题
在n×n的棋盘上放置n个皇后，使得每个皇后不在同一行、同一列或同一斜线上:
def solve_n_queens(n):
def is_safe(row, col):
for i in range(row):
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
def backtrack(row):
if row == n:
solutions.append(board[:])
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1)
board[row] = -1
solutions = []
board = [-1] * n
backtrack(0)
return solutions
时间复杂度：O(n!)
8.5 分支限界法¶
分支限界法的思想
在回溯法基础上引入限界函数，剪掉不可能得到最优解的分支。
分支限界法的步骤
定义限界函数
选择搜索策略（广度优先、最佳优先）
生成子节点
计算下界
剪枝或继续搜索
典型应用
旅行商问题
装箱问题
调度问题
9. 应用领域¶
9.1 操作系统¶
- 内存管理
分区分配、分页、分段
使用链表、树等数据结构管理内存块
- 进程调度
使用队列实现进程调度
使用堆实现优先级调度
- 文件系统
使用树结构组织文件和目录
9.2 数据库系统¶
- 索引
B树、B+树索引
哈希索引
- 查询优化
排序算法
哈希连接
- 事务管理
使用日志和锁实现并发控制
9.3 网络编程¶
- 路由算法
Dijkstra算法
距离矢量算法
- 数据包处理
使用队列实现缓冲
使用哈希表实现连接管理
9.4 图形学¶
- 几何算法
凸包算法
线段相交检测
- 渲染
使用树结构（BSP树、四叉树、八叉树）组织场景
使用图结构表示网格
10. 总结与展望¶
数据结构与算法是计算机科学的基石，是编写高效、可靠程序的基础。从数组到图，从排序到动态规划，掌握数据结构与算法将极大提升你的编程能力。
核心价值
提高程序效率
优化资源使用
解决复杂问题
提升代码质量
学习建议
理解基本概念和原理
多动手实现数据结构和算法
分析算法的时间和空间复杂度
解决实际问题
参加算法竞赛
进阶方向
高级数据结构（并查集、线段树、树状数组、后缀数组等）
算法优化技巧
并行算法
随机算法
机器学习算法
数据结构与算法是程序员必备的核心技能，掌握它们将让你在编程道路上走得更远。