算法学习库 / Algorithm Learning Library

中文 | English

---

中文文档

📚 项目简介

这是一个全面的算法和数据结构学习库，用 C 语言实现了常见的算法和数据结构。本项目旨在帮助学习者理解算法原理、分析时间复杂度，并提供可运行的示例代码。

每个算法都配有：

• ✅ 详细的中英文注释
• ✅ 时间和空间复杂度分析
• ✅ 实际运行示例
• ✅ 性能测试功能

🗂️ 项目结构

algorithm/
├── README.md                    # 本文档
├── ALGORITHMS.md                # 算法复杂度对比表
├── CMakeLists.txt              # CMake 构建配置
├── main.c                      # 主程序（交互式菜单）
│
├── include/                    # 头文件目录
│   ├── sort.h                  # 排序算法声明
│   ├── search.h                # 搜索算法声明
│   ├── data_structures.h       # 数据结构声明
│   ├── classic_algorithms.h    # 经典算法声明
│   └── utils.h                 # 工具函数声明
│
└── src/                        # 源文件目录
    ├── sort.c                  # 排序算法实现
    ├── search.c                # 搜索算法实现
    ├── data_structures.c       # 数据结构实现
    ├── classic_algorithms.c    # 经典算法实现
    └── utils.c                 # 工具函数实现

🎯 包含的算法

1️⃣ 排序算法 (10种)

算法	平均时间	最坏时间	空间复杂度	稳定性
冒泡排序 (Bubble Sort)	O(n²)	O(n²)	O(1)	稳定
选择排序 (Selection Sort)	O(n²)	O(n²)	O(1)	不稳定
插入排序 (Insertion Sort)	O(n²)	O(n²)	O(1)	稳定
希尔排序 (Shell Sort)	O(n log n)	O(n²)	O(1)	不稳定
快速排序 (Quick Sort)	O(n log n)	O(n²)	O(log n)	不稳定
归并排序 (Merge Sort)	O(n log n)	O(n log n)	O(n)	稳定
堆排序 (Heap Sort)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序 (Counting Sort)	O(n+k)	O(n+k)	O(k)	稳定
桶排序 (Bucket Sort)	O(n+k)	O(n²)	O(n+k)	稳定
基数排序 (Radix Sort)	O(d·(n+k))	O(d·(n+k))	O(n+k)	稳定

2️⃣ 搜索算法

• 线性搜索 (Linear Search) - O(n)
• 二分搜索 (Binary Search) - O(log n)
• 插值搜索 (Interpolation Search) - O(log log n)

3️⃣ 数据结构

• 单向链表 (Singly Linked List)
• 双向链表 (Doubly Linked List)
• 栈 (Stack) - LIFO
• 队列 (Queue) - FIFO
• 二叉搜索树 (Binary Search Tree)
• 二叉树遍历 (Tree Traversal: 前序/中序/后序)

4️⃣ 经典算法

• 最大公约数 (GCD - Euclidean Algorithm)
• 最小公倍数 (LCM)
• 斐波那契数列 (Fibonacci Sequence)
• 素数判定 (Prime Number Check)
• 动态规划示例 (Dynamic Programming Examples)
  • 背包问题 (Knapsack Problem)
  • 最长公共子序列 (LCS)
  • 爬楼梯问题 (Climbing Stairs)

🔧 编译和运行

前置要求

• GCC 或 Clang 编译器
• CMake 3.15 或更高版本

编译步骤

# 1. 创建构建目录
mkdir -p build && cd build

# 2. 生成 Makefile
cmake ..

# 3. 编译项目
make

# 4. 运行程序
./algorithm

或者使用一键脚本：

cmake -B build && cmake --build build && ./build/algorithm

📖 使用指南

程序启动后会显示交互式菜单：

========================================
    算法学习库 / Algorithm Library
========================================
1. 排序算法演示
2. 搜索算法演示
3. 数据结构演示
4. 经典算法演示
5. 性能对比测试
0. 退出程序
========================================
请选择 (0-5):

🎓 学习路径建议

初学者路径

1. 从简单排序开始：冒泡排序 → 选择排序 → 插入排序
2. 理解递归：归并排序 → 快速排序
3. 学习基础数据结构：链表 → 栈 → 队列
4. 掌握搜索算法：线性搜索 → 二分搜索

进阶路径

1. 高效排序算法：堆排序 → 计数排序 → 基数排序
2. 树形结构：二叉搜索树 → AVL 树
3. 动态规划：斐波那契 → 背包问题 → LCS
4. 图算法：DFS → BFS → 最短路径

💡 代码风格说明

本项目遵循以下编码规范：

• 命名规范：驼峰命名法 (camelCase)
• 注释：中英文双语注释
• 缩进：4 个空格
• 标准：C99 标准

🔍 性能测试

每个算法都包含性能测试功能，可以：

• 测量执行时间
• 统计比较次数
• 统计交换次数
• 分析不同数据规模下的性能

📊 复杂度分析

详细的时间和空间复杂度分析请查看 ALGORITHMS.md

---

English Documentation

📚 Project Overview

This is a comprehensive Algorithm and Data Structure Learning Library implemented in C. The project aims to help learners understand algorithm principles, analyze time complexity, and provide runnable example code.

Each algorithm includes:

• ✅ Detailed bilingual (Chinese/English) comments
• ✅ Time and space complexity analysis
• ✅ Practical running examples
• ✅ Performance testing features

🗂️ Project Structure

See the structure diagram in the Chinese section above.

🎯 Included Algorithms

1️⃣ Sorting Algorithms (10 types)

• Bubble Sort - O(n²) time, O(1) space, stable
• Selection Sort - O(n²) time, O(1) space, unstable
• Insertion Sort - O(n²) time, O(1) space, stable
• Shell Sort - O(n log n) average time, unstable
• Quick Sort - O(n log n) average time, unstable
• Merge Sort - O(n log n) time, O(n) space, stable
• Heap Sort - O(n log n) time, O(1) space, unstable
• Counting Sort - O(n+k) time, O(k) space, stable
• Bucket Sort - O(n+k) average time, stable
• Radix Sort - O(d·(n+k)) time, stable

2️⃣ Search Algorithms

• Linear Search - O(n)
• Binary Search - O(log n)
• Interpolation Search - O(log log n)

3️⃣ Data Structures

• Singly Linked List
• Doubly Linked List
• Stack (LIFO)
• Queue (FIFO)
• Binary Search Tree
• Tree Traversal (Preorder/Inorder/Postorder)

4️⃣ Classic Algorithms

• Greatest Common Divisor (GCD)
• Least Common Multiple (LCM)
• Fibonacci Sequence
• Prime Number Check
• Dynamic Programming Examples
  • Knapsack Problem
  • Longest Common Subsequence (LCS)
  • Climbing Stairs

🔧 Build and Run

Prerequisites

• GCC or Clang compiler
• CMake 3.15 or higher

Build Steps

# 1. Create build directory
mkdir -p build && cd build

# 2. Generate Makefile
cmake ..

# 3. Compile project
make

# 4. Run program
./algorithm

Or use one-liner:

cmake -B build && cmake --build build && ./build/algorithm

📖 Usage Guide

After starting the program, an interactive menu will be displayed allowing you to explore different categories of algorithms and data structures.

🎓 Learning Path

Beginner Path

1. Start with simple sorting: Bubble → Selection → Insertion
2. Understand recursion: Merge Sort → Quick Sort
3. Learn basic data structures: Linked List → Stack → Queue
4. Master search algorithms: Linear → Binary Search

Advanced Path

1. Efficient sorting: Heap Sort → Counting Sort → Radix Sort
2. Tree structures: Binary Search Tree → AVL Tree
3. Dynamic programming: Fibonacci → Knapsack → LCS
4. Graph algorithms: DFS → BFS → Shortest Path

💡 Code Style

This project follows:

• Naming convention: camelCase
• Comments: Bilingual (Chinese/English)
• Indentation: 4 spaces
• Standard: C99

📝 License

This project is for educational purposes. Feel free to use and modify for learning.

🤝 Contributing

Contributions are welcome! Feel free to:

• Add new algorithms
• Improve documentation
• Fix bugs
• Optimize implementations

---

Happy Learning! 祝学习愉快！ 🚀