数据结构教程（二）- 非线性结构
数据结构教程（C语言版）¶
第四部分：树 (Tree)¶
4.1 什么是树？¶
在现实世界中，树有树根、树枝和树叶。计算机科学中的“树”结构是对这种层次关系的一种抽象模拟。它是一种非线性的数据结构，用于表示具有层级关系的数据。
与每个元素最多只有一个前驱和一个后继的线性结构不同，树中的一个节点可以有多个后继（称为子节点）。
最常见的例子就是电脑里的文件系统：一个根目录（/ 或 C:）下有多个文件夹（子节点），每个文件夹下又可以有更多的文件夹和文件。
4.2 树的核心术语¶
- 节点 (Node): 树的基本组成部分，包含数据和指向其他节点的指针。
* 根 (Root): 树的最顶层节点，一棵树只有一个根节点。
* 边 (Edge):连接两个节点的线。
* 父节点 (Parent): 一个节点的直接上层节点。
* 子节点 (Child): 一个节点的直接下层节点。
* 兄弟节点 (Sibling): 拥有相同父节点的节点。
* 叶节点 (Leaf): 没有任何子节点的节点（度为0的节点）。
* 内部节点 (Internal Node): 至少有一个子节点的节点（非叶节点）。
* 高度 (Height): 从一个节点到其最远叶节点的最长路径上的边的数量。树的高度是根节点的高度。
* 深度 (Depth): 从根节点到一个节点的路径上的边的数量。根节点的深度为0。
* 子树 (Subtree): 树中某个节点及其所有后代组成的结构。
4.3 二叉树 (Binary Tree)¶
在众多树的类型中，二叉树是最基础和最常用的一种。
定义：二叉树是每个节点最多有两个子节点的树结构。这两个子节点通常被称为“左子节点 (left child)”和“右子节点 (right child)”。
#### 4.3.1 二叉树的C语言表示
与链表类似，我们使用结构体和指针来表示二叉树的节点。
codeC
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
struct TreeNode {
int data; // 节点存储的数据
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
// 创建一个新节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
4.3.2 二叉树的遍历 (Traversal)¶
如何访问树中的每一个节点，并且每个节点只访问一次？这就是树的遍历。主要有两种策略：深度优先搜索 (DFS) 和 广度优先搜索 (BFS)。
1. 深度优先搜索 (DFS)
DFS 会尽可能深地探索树的分支。它有三种常见的遍历顺序，通常用递归实现，非常简洁。
-
前序遍历 (Pre-order): 根 -> 左 -> 右
-
访问根节点。
- 递归地前序遍历左子树。
- 递归地前序遍历右子树。
codeC
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); // 访问根
preorderTraversal(root->left); // 遍历左
preorderTraversal(root->right); // 遍历右
}
- 递归地中序遍历左子树。
- 访问根节点。
- 递归地中序遍历右子树。
codeC
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left); // 遍历左
printf("%d ", root->data); // 访问根
inorderTraversal(root->right); // 遍历右
}
- 递归地后序遍历左子树。
- 递归地后序遍历右子树。
- 访问根节点。 （应用：可以用来释放整棵树的内存，因为可以保证在释放父节点之前，其子节点已经被处理）。
codeC
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left); // 遍历左
postorderTraversal(root->right); // 遍历右
printf("%d ", root->data); // 访问根
}
2. 广度优先搜索 (BFS) / 层序遍历 (Level-order)
BFS 从根节点开始，逐层地访问节点。它需要借助队列来实现。
- 创建一个队列，并将根节点入队。
- 当队列不为空时，循环执行： a. 将队头节点出队并访问它。 b. 如果该节点有左子节点，则将其左子节点入队。 c. 如果该节点有右子节点，则将其右子节点入队。
4.4 二叉搜索树 (Binary Search Tree - BST)¶
普通的二叉树没有对节点的数据值做任何限制。而二叉搜索树 (BST) 增加了一个重要的规则，使得查找操作变得极其高效。
BST 属性: 对于树中的任意一个节点：
- 其左子树中所有节点的值都小于该节点的值。
- 其右子树中所有节点的值都大于该节点的值。
- 它的左、右子树也分别是二叉搜索树。
重要特性：对一个二叉搜索树进行中序遍历，会得到一个有序的元素序列。
#### 4.4.1 BST 的核心操作
1. 查找 (Search)
利用BST属性，查找过程非常快。
- 从根节点开始。
- 如果要查找的值等于当前节点的值，则查找成功。
- 如果要查找的值小于当前节点的值，则在左子树中继续查找。
- 如果要查找的值大于当前节点的值，则在右子树中继续查找。
- 如果遇到 NULL，则说明树中不存在该值。
codeC
struct TreeNode* search(struct TreeNode* root, int key) {
if (root == NULL || root->data == key) {
return root;
}
if (key < root->data) {
return search(root->left, key);
}
return search(root->right, key);
}```
**2. 插入 (Insertion)**
插入操作与查找类似。我们首先查找到新元素应该被插入的位置（即查找到一个 `NULL` 链接），然后将新节点插入到该位置。
```c
struct TreeNode* insert(struct TreeNode* root, int data) {
// 如果树为空，则返回一个新节点
if (root == NULL) {
return createNode(data);
}
// 否则，在树中递归地向下查找
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
// 返回（可能未被修改的）节点指针
return root;
}
3. 删除 (Deletion)
删除是BST中最复杂的操作，需要分三种情况讨论：
- Case 1: 要删除的节点是叶节点 (无子节点) 直接释放该节点，并将其父节点的对应链接（左或右）设为 NULL。
- Case 2: 要删除的节点只有一个子节点 用其子节点替代它。即将该节点的父节点直接链接到该节点的子节点上，然后释放该节点。
-
Case 3: 要删除的节点有两个子节点 这是最复杂的情况。为了维持BST的属性，我们不能简单地删除它。
-
找到该节点的中序后继（In-order Successor），即其右子树中的最小节点。
* 将中序后继节点的值复制到要删除的节点上。 * 递归地删除那个中序后继节点（此时问题被转化为删除一个最多只有一个子节点的节点）。
4.5 总结¶
- 树是一种表示层级关系的强大非线性数据结构。
- 二叉树是每个节点最多有两个子节点的特殊树。
- 树的遍历是基础操作，分为深度优先 (前序、中序、后序) 和广度优先 (层序)。
- 二叉搜索树 (BST) 增加了值的排序规则，使得查找、插入、删除操作的平均时间复杂度都为 O(h)，其中 h 是树的高度。
* 对于一个平衡的BST（左右子树高度差不大），其高度约为 log(n)，因此操作非常高效，接近 O(log n)。但如果BST变得极不平衡（例如退化成一条链表），其性能会下降到 O(n)。这也引出了更高级的自平衡二叉搜索树，如 AVL 树和红黑树。
第五部分：哈希表 (Hash Table)¶
5.1 什么是哈希表？¶
哈希表，又称散列表，是一种通过键 (Key) 来直接访问其对应值 (Value) 的数据结构。它建立了一种键值对 (Key-Value Pair) 的映射关系。
想象一下一本英文字典。如果你想查找单词 "apple"，你不会从第一页的 "abandon" 开始一页一页地翻。你会直接翻到字母 'A' 的部分，然后快速定位到 "apple"。哈希表的工作原理与此类似，但更进一步。它试图通过一个“魔法函数”直接计算出任何一个键应该存放的精确位置。
这个“魔法函数”就是哈希函数，它将任意长度的输入（键）转换成一个固定长度的输出（数组的索引）。
#### 5.2 哈希表的核心组成
一个哈希表主要由两个核心部分组成：
- 数组 (Array): 这是哈希表的底层存储结构，通常被称为桶数组 (Bucket Array)。数组中的每一个位置就是一个“桶 (Bucket)”。
* 哈希函数 (Hash Function): 这是一个函数，它的职责是接收一个键作为输入，并返回一个整数，这个整数就是该键在桶数组中对应的索引。
理想过程：
- 插入: insert("apple", "A round fruit")
哈希函数计算 hash("apple") -> 得到索引 4*。
- 将 "A round fruit" 这个值存放到数组的第 4 个位置。
- 查找: search("apple")
哈希函数再次计算 hash("apple") -> 得到索引 4*。
- 直接去数组的第 4 个位置取出值，操作完成。
这个过程非常快，因为只涉及一次函数计算和一次数组访问，时间复杂度为 O(1)。
5.3 哈希冲突 (Hash Collision)¶
理想是美好的，但现实是骨感的。由于桶数组的大小是有限的，而键的可能取值是近乎无限的，不可避免地会出现这样一种情况：两个不同的键，经过哈希函数计算后，得到了相同的索引。这种情况被称为哈希冲突。
例如，hash("apple") -> 4，同时 hash("banana") -> 4。当我们要把 "banana" 存入时，发现第 4 个桶已经被 "apple" 占用了。
解决哈希冲突是设计哈希表的关键所在。最常用的一种策略是拉链法 (Separate Chaining)。
#### 5.4 冲突解决方法：拉链法 (Separate Chaining)
拉链法的思想很简单：数组的每个桶不再是直接存储一个元素，而是存储一个指向链表头的指针。
当一个新元素被哈希到某个索引时，我们检查该索引处的链表。*
- 如果发生冲突，这个新元素就被简单地添加到这个链表的末尾（或开头）。
- 当查找一个元素时，我们先通过哈希函数找到对应的桶（链表），然后遍历这个短小的链表来找到我们需要的键。
5.5 哈希表的 C 语言实现 (拉链法)¶
1. 定义数据结构
我们需要两个结构体：一个用于表示链表节点（存储键值对），另一个用于表示整个哈希表。
codeC
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 // 定义哈希表的大小
// 链表节点，用于存储键值对
struct HashNode {
char* key;
int value;
struct HashNode* next;
};
// 哈希表结构
struct HashTable {
int size;
struct HashNode** table; // 指向 HashNode 指针数组的指针
};
2. 哈希函数
这里我们实现一个简单的哈希函数，它将字符串中所有字符的ASCII码值相加，然后对表的大小取模。 (注意：在实际应用中，会使用更复杂的哈希函数以获得更好的分布效果，如 djb2, sdbm 等)
codeC
// 简单的哈希函数
unsigned int hashFunction(char* key, int size) {
unsigned long int hash = 0;
int c;
while ((c = *key++)) {
hash += c;
}
return hash % size;
}
3. 核心操作
codeC
// 创建哈希表
struct HashTable* createHashTable(int size) {
struct HashTable* ht = (struct HashTable*)malloc(sizeof(struct HashTable));
ht->size = size;
ht->table = (struct HashNode**)malloc(sizeof(struct HashNode*) * size);
// 初始化所有桶（链表头）为 NULL
for (int i = 0; i < size; i++) {
ht->table[i] = NULL;
}
return ht;
}
// 插入操作
void insert(struct HashTable* ht, char* key, int value) {
unsigned int index = hashFunction(key, ht->size);
struct HashNode* current = ht->table[index];
// 检查键是否已存在，如果存在则更新值
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
current->value = value;
return;
}
current = current->next;
}
// 如果键不存在，则在链表头部插入新节点
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = strdup(key); // 复制字符串
newNode->value = value;
newNode->next = ht->table[index];
ht->table[index] = newNode;
}
// 查找操作
int search(struct HashTable* ht, char* key) {
unsigned int index = hashFunction(key, ht->size);
struct HashNode* current = ht->table[index];
// 遍历对应索引的链表
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value; // 找到了
}
current = current->next;
}
return -1; // 未找到，返回一个特殊值
}
// 删除操作 (篇幅原因，此处省略，其逻辑为：先查找，找到后执行标准链表删除)
// 释放哈希表 (非常重要，防止内存泄漏)
void freeHashTable(struct HashTable* ht) {
for (int i = 0; i < ht->size; i++) {
struct HashNode* current = ht->table[i];
while (current != NULL) {
struct HashNode* temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(ht->table);
free(ht);
}
5.6 性能分析¶
- 加载因子 (Load Factor): 这是衡量哈希表“满”的程度的指标，计算公式为 α = n / m (n = 已存储的元素数量, m = 桶的数量)。加载因子直接影响哈希表的性能。
* 时间复杂度:
平均情况: 查找、插入和删除都是 O(1 + α)。如果哈希函数分布均匀且加载因子 α 是一个较小的常数（通常建议保持在 0.75 以下），那么性能就接近 O(1)*。
-
最坏情况: 如果哈希函数设计得极差，导致所有键都冲突并映射到同一个桶，那么哈希表就退化成了一个链表。此时，所有操作的时间复杂度都将是 O(n)。
5.7 总结¶
- 哈希表是一种以空间换时间的高效数据结构，提供了极快的平均查找、插入和删除速度。
- 其核心是哈希函数和冲突解决策略。
* 拉链法是解决冲突最常用和最稳健的方法之一。 * 哈希表的性能高度依赖于一个好的哈希函数和一个合适的加载因子。
* 它被广泛应用于各种场景，如数据库索引、缓存系统、编程语言中的字典/map/对象实现等。几乎所有需要快速通过键查找值的场景，背后都有哈希表的影子。
第六部分：图 (Graph)¶
6.1 什么是图？¶
图是一种非线性数据结构，由一组顶点 (Vertices) 和一组连接顶点的边 (Edges) 组成。形式上，一个图 G 可以表示为 G = (V, E)，其中 V 是顶点集，E 是边集。
与树不同，图的规则要宽松得多：
- 图不一定有根节点。
* 图中的节点可以有任意数量的连接。 * 图可以包含环路 (Cycle)，即从一个顶点出发，沿着一系列边可以回到该顶点。
* 图可以是不连通的 (Disconnected)，即图中可能存在无法通过边相互到达的顶点组。
现实世界的例子：
- 社交网络: 用户是顶点，好友关系是边。
* 地图系统:城市/交叉路口是顶点，道路是边。
* 万维网: 网页是顶点，超链接是边。
* 航空公司网络: 机场是顶点，航线是边。
6.2 图的核心术语¶
- 顶点 (Vertex): 也称为节点 (Node)。
* 边 (Edge): 连接两个顶点的线。
* 无向图 (Undirected Graph): 边没有方向。如果顶点 A 和 B 之间有一条边，那么可以从 A 到 B，也可以从 B 到 A。社交网络中的好友关系就是无向的。
* 有向图 (Directed Graph / Digraph): 边有方向。一条从 A 指向 B 的边，表示可以从 A 到 B，但不能从 B 到 A（除非存在另一条反向的边）。网页的超链接就是有向的。
* 权重 (Weight): 可以给边赋予一个数值，称为权重或成本。例如，在地图中，边的权重可以代表两个城市间的距离或旅行时间。有权重的图称为加权图 (Weighted Graph)。
* 邻接 (Adjacent): 如果两个顶点之间有一条边直接相连，则称它们是邻接的。
* 度 (Degree): 在无向图中，一个顶点的度是指与该顶点相连的边的数量。在有向图中，分为入度 (In-degree)（指向该顶点的边的数量）和出度 (Out-degree)（从该顶点出发的边的数量）。
* 路径 (Path): 从一个顶点到另一个顶点经过的边构成的序列。
* 环 (Cycle): 一条起点和终点相同的路径。
6.3 图的表示方法¶
如何在代码中存储一个图？主要有两种标准方法：邻接矩阵和邻接表。
1. 邻接矩阵 (Adjacency Matrix)
一个 V x V 的二维数组（其中 V 是顶点的数量），matrix[i][j] 的值表示顶点 i 和顶点 j 之间的关系。
- 对于无权图，如果 i 和 j 之间有边，则 matrix[i][j] = 1，否则为 0。
* 对于加权图，matrix[i][j] 存储的是边的权重，没有边则可以用一个特殊值（如无穷大或0）表示。
* 对于无向图，这个矩阵是对称的（matrix[i][j] = matrix[j][i]）。
优点:
检查两个顶点之间是否存在边非常快，时间复杂度为 O(1)。*
- 实现简单直观。 缺点:
* 空间复杂度为 O(V²)，当顶点很多但边很少时（稀疏图），会浪费大量内存。
codeC
// 邻接矩阵表示
#define V 5
int adjMatrix[V][V]; // 初始化为 0
// 添加一条从 0 到 1 的边
adjMatrix[0][1] = 1;
adjMatrix[1][0] = 1; // 如果是无向图
2. 邻接表 (Adjacency List)
一个由 V 个链表组成的数组。数组的第 i 个元素 adjList[i] 是一个链表，存储了所有与顶点 i 相邻接的顶点。
优点:
空间效率高，特别是对于稀疏图，空间复杂度为 O(V + E)（E是边的数量）。*
- 遍历一个顶点的所有邻居非常方便。 缺点:
* 检查两个顶点 u 和 v 之间是否存在边，需要遍历 adjList[u] 这个链表，时间复杂度为 O(Degree(u))。
这是在实践中最常用的图表示方法。
codeC
#include <stdio.h>
#include <stdlib.h>
// 邻接表节点
struct AdjListNode {
int dest; // 目标顶点
struct AdjListNode* next;
};
// 邻接表
struct AdjList {
struct AdjListNode *head; // 指向链表头的指针
};
// 图结构
struct Graph {
int V; // 顶点数
struct AdjList* array;
};
// 创建一个图
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// 添加一条边 (用于无向图)
void addEdge(struct Graph* graph, int src, int dest) {
// 从 src 到 dest 的边
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// 从 dest 到 src 的边
newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = src;
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
6.4 图的遍历¶
图的遍历是从某个顶点出发，访问图中所有可达顶点的过程，且每个顶点只访问一次。最核心的两种算法是广度优先搜索 (BFS) 和深度优先搜索 (DFS)。
1. 广度优先搜索 (BFS - Breadth-First Search)
BFS 从一个起始顶点开始，逐层向外扩展。它首先访问所有与起始顶点直接相邻的邻居，然后访问这些邻居的邻居，以此类推。这就像在水中投下一颗石子，波纹一圈一圈向外扩散。
BFS 需要使用一个队列 (Queue) 来实现。
算法步骤:
- 创建一个队列和一个 visited 数组（用于标记已访问的顶点）。
- 选择一个起始顶点 s，将其标记为已访问，并将其入队。
- 当队列不为空时，循环执行： a. 将队头顶点 u 出队。 b. 访问 u（例如打印它）。 c. 遍历 u 的所有未被访问过的邻居 v，将它们标记为已访问，并依次入队。
应用:
在无权图中寻找两个顶点之间的最短路径。*
- 社交网络中寻找“K度好友”。
2. 深度优先搜索 (DFS - Depth-First Search)
DFS 从起始顶点开始，沿着一条路径尽可能深地探索，直到到达一个末端，然后回溯到上一个节点，继续探索其他未被访问的分支。这就像在走迷宫时，沿着一条路走到死胡同，然后返回到上一个路口选择另一条路。
DFS 通常使用递归来实现（隐式地使用了系统调用栈），也可以用一个显式的栈 (Stack) 来实现。
算法步骤 (递归版):
- 创建一个 visited 数组。
- 选择一个起始顶点 u。
- 定义一个递归函数 DFS(u): a. 将 u 标记为已访问并访问它。 b. 对于 u 的每一个未被访问过的邻居 v，递归调用 DFS(v)。
应用:
检测图中是否存在环*。
- 拓扑排序（用于有向无环图）。
- 寻找图的连通分量。
6.5 总结¶
- 图是用于建模网络关系的最通用数据结构，由顶点和边组成。
- 在代码中，图最常用邻接表来表示，因为它对大多数应用场景（特别是稀疏图）来说空间效率更高。
- BFS 和 DFS 是遍历图的两种基本且强大的算法，它们是许多其他复杂图算法的基础。
- BFS 使用队列，按层级顺序探索，能找到无权图中的最短路径。
* DFS 使用栈（或递归），进行深度探索，适合用于检测环或拓扑排序等任务。
掌握图是数据结构学习的一个重要里程碑，它为你解决现实世界中更广泛、更复杂的问题打开了大门。
第七部分：排序算法 (Sorting Algorithms)¶
排序是计算机科学中最基础也是最重要的操作之一。排序算法的目标是将一组数据按照特定的顺序（通常是升序）排列。
7.1 排序算法的分类¶
1. 内部排序 vs 外部排序 * 内部排序: 所有数据都可以加载到内存中 * 外部排序: 数据量太大，无法全部加载到内存，需要使用外部存储
2. 稳定排序 vs 不稳定排序 * 稳定排序: 相同值的元素在排序后保持相对顺序 * 不稳定排序: 相同值的元素在排序后可能改变相对顺序
3. 时间复杂度分类 * O(n²) 算法: 冒泡排序、选择排序、插入排序 * O(n log n) 算法: 快速排序、归并排序、堆排序 * O(n) 算法: 计数排序、基数排序（特殊条件）
7.2 基础排序算法¶
1. 冒泡排序 (Bubble Sort)
原理: 重复遍历数组，比较相邻元素，如果顺序错误就交换它们。每次遍历都会将最大的元素"冒泡"到末尾。
时间复杂度: O(n²) 空间复杂度: O(1) 稳定性: 稳定
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 优化：如果某次遍历没有发生交换，说明已经有序
int swapped = 0;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break; // 提前退出
}
}
2. 选择排序 (Selection Sort)
原理: 每次从未排序部分选择最小元素，放到已排序部分的末尾。
时间复杂度: O(n²) 空间复杂度: O(1) 稳定性: 不稳定
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 找到未排序部分的最小元素
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 将最小元素交换到正确位置
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}
3. 插入排序 (Insertion Sort)
原理: 将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。
时间复杂度: O(n²) 空间复杂度: O(1) 稳定性: 稳定
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将大于 key 的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
7.3 高级排序算法¶
1. 快速排序 (Quick Sort)
原理: 选择一个基准元素（pivot），将数组分为两部分，小于基准的放左边，大于基准的放右边，然后递归地对两部分进行排序。
时间复杂度: 平均 O(n log n)，最坏 O(n²) 空间复杂度: O(log n) 稳定性: 不稳定
// 分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 小于基准的元素的索引
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high]（基准）
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// 快速排序主函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// 获取分区索引
int pi = partition(arr, low, high);
// 递归排序分区
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
2. 归并排序 (Merge Sort)
原理: 将数组分成两半，分别排序，然后合并两个已排序的子数组。
时间复杂度: O(n log n) 空间复杂度: O(n) 稳定性: 稳定
// 合并两个已排序的子数组
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组
int L[n1], R[n2];
// 复制数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 合并临时数组
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序主函数
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
// 递归排序两半
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// 合并已排序的两半
merge(arr, l, m, r);
}
}
3. 堆排序 (Heap Sort)
原理: 利用堆这种数据结构进行排序。首先建立最大堆，然后反复取出堆顶元素（最大值），放到数组末尾。
时间复杂度: O(n log n) 空间复杂度: O(1) 稳定性: 不稳定
// 堆化函数
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大元素为根
int left = 2 * i + 1;
int right = 2 * i + 2;
// 如果左子节点大于根
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点大于当前最大
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大不是根
if (largest != i) {
// 交换
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归堆化受影响的子树
heapify(arr, n, largest);
}
}
// 堆排序主函数
void heapSort(int arr[], int n) {
// 建立最大堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 逐个提取元素
for (int i = n - 1; i > 0; i--) {
// 移动当前根到末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 在减少的堆上调用 heapify
heapify(arr, i, 0);
}
}
7.4 线性时间排序算法（特殊条件）¶
1. 计数排序 (Counting Sort)
原理: 统计每个元素出现的次数，然后根据计数输出排序结果。
时间复杂度: O(n + k)（k是取值范围） 空间复杂度: O(k) 适用条件: 元素必须是整数，且范围有限
void countingSort(int arr[], int n) {
// 找到最大元素
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
// 创建计数数组
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
// 统计每个元素的出现次数
for (int i = 0; i < n; i++)
count[arr[i]]++;
// 修改计数数组，存储实际位置
for (int i = 1; i <= max; i++)
count[i] += count[i - 1];
// 构建输出数组
int output[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// 复制到原数组
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
7.5 排序算法比较¶
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 数据量小，基本有序 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 数据量小，交换成本高 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 数据量小，基本有序 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用，平均性能最好 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据量，需要稳定排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存有限 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 稳定 | 整数，范围有限 |
7.6 竞赛级排序技巧¶
1. 快速排序的优化
// 三数取中法选择基准
int medianOfThree(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
// 对三个元素进行排序
if (arr[low] > arr[mid])
swap(&arr[low], &arr[mid]);
if (arr[mid] > arr[high])
swap(&arr[mid], &arr[high]);
if (arr[low] > arr[mid])
swap(&arr[low], &arr[mid]);
return mid; // 返回中间值的索引
}
// 小数组使用插入排序（通常 n < 10）
void insertionSortRange(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
2. 归并排序的迭代实现（避免递归栈溢出）
void mergeSortIterative(int arr[], int n) {
int curr_size; // 当前子数组大小，从1到n/2
int left_start; // 左子数组的起始索引
// 合并大小为curr_size的子数组
// 第一次合并：curr_size = 1，第二次：curr_size = 2，等等
for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {
// 从左到右合并子数组
for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
int mid = left_start + curr_size - 1;
int right_end = (left_start + 2 * curr_size - 1) < (n - 1) ?
(left_start + 2 * curr_size - 1) : (n - 1);
merge(arr, left_start, mid, right_end);
}
}
}
7.7 练习题目¶
基础练习： 1. 实现冒泡排序、选择排序、插入排序 2. 实现快速排序、归并排序、堆排序 3. 比较不同排序算法在相同数据上的性能
进阶练习： 4. 实现稳定的快速排序 5. 实现基数排序 6. 对字符串数组进行字典序排序 7. 实现对结构体数组的排序（按多个字段）
竞赛练习： 8. 求逆序对数量（使用归并排序） 9. 快速选择算法（找出第k小的元素） 10. 外部排序实现（处理大数据集）
恭喜你完成了数据结构教程的学习！你已经掌握了编程中最核心的数据结构和算法知识。继续加油，在竞赛中取得好成绩！