算法学习笔记

这是我的算法学习笔记仓库，记录了算法学习过程中的知识点、代码实现和练习题。

📺 学习资源

本仓库内容主要参考自左程云老师的算法课程：

• 【算法】大厂算法和数据结构刷题班

📚 目录结构

01-入门/
├── 1.1-复杂度/
│   └── README.md          # 时间复杂度和空间复杂度
├── 1.2-常见的排序算法/
│   ├── README.md          # 排序算法总览
│   ├── 代码/              # 排序算法实现
│   ├── 算法题/            # 相关算法题
│   └── 对数器/            # 对数器工具
└── 1.3-二分/
    ├── README.md          # 二分查找详解
    └── 算法题/            # 二分相关算法题

✅ 已完成内容

1.1 复杂度

• 时间复杂度基本概念和计算规则
• 空间复杂度基本概念
• 时间与空间的权衡

1.2 常见的排序算法

• 选择排序：基础排序算法，时间复杂度 O(n²)
• 冒泡排序：经典排序算法，时间复杂度 O(n²)
• 插入排序：适合小规模数据的排序，时间复杂度 O(n²)
• 归并排序：分治算法，时间复杂度 O(n log n)
  • 小和问题
  • 逆序对问题
  • 右侧小于当前元素的个数
• 快速排序：高效排序算法，平均时间复杂度 O(n log n)
  • 荷兰国旗问题（三路快排基础）
• 堆排序：基于堆结构的排序，时间复杂度 O(n log n)，空间复杂度 O(1)
  • 堆结构（大根堆/小根堆）
  • heapInsert（向上调整）和 heapify（向下调整）
  • 排序几乎有序的数组（O(n log k) 优化）
• 基数排序：非比较排序，时间复杂度 O(d×n)
  • LSD（从低位到高位）
  • 计数排序思想
• 比较器：自定义排序规则（Comparator vs Comparable）
• 排序算法总结：7种排序算法的复杂度对比与选择建议
• 异或交换：不使用临时变量的交换技巧
• 对数器：自动化测试工具

1.3 二分查找

• 二分查找基础：理解二分的本质
• 题目1：在有序数组中查找目标值
• 题目2：找大于等于某个数的最左侧位置
• 题目3：局部最小值问题（无序数组也能用二分）

🎯 学习方法

1. 理论学习：阅读 README.md 理解算法原理
2. 代码实现：自己动手实现算法
3. 对数器验证：用对数器测试代码正确性
4. 算法题练习：通过题目巩固知识

📝 更新日志

2026-07-20

• 堆排序：完整实现堆结构和堆排序算法
  • 新增 Heap.java：大根堆实现（heapInsert、heapify、push、pop、modify）
  • 新增 HeapSort.java：堆排序实现（O(n log n)时间，O(1)空间）
  • 新增算法题：排序几乎有序的数组（O(n log k)优化）
• 基数排序：非比较型整数排序算法
  • 新增 RadixSort.java：基数排序完整实现（LSD从低位到高位）
  • 详细讲解计数排序思想、前缀和技巧、稳定性保证
• 比较器教程：新增 比较器/README.md
  • Comparator vs Comparable 详解
  • 自定义排序规则的最佳实践
  • 常见场景和注意事项
• 排序算法总结：新增排序算法总结对比章节
  • 7种排序算法的复杂度对比表格
  • 稳定性、原地排序、时间空间权衡分析
  • 算法选择建议（根据数据特征和需求）
  • 实际工程中的排序策略（Java/C++/Python）

2026-07-19

• 复杂度部分：新增Master定理内容和应用示例
• 归并排序：完整实现及复杂度分析
  • 新增算法拓展：小和问题
  • 新增算法拓展：逆序对问题
  • 新增算法拓展：右侧小于当前元素的个数
• 快速排序：完整实现（随机pivot + 双指针partition）
  • 新增三路快排实现（优化重复元素情况）
  • 新增荷兰国旗问题（三路划分）
• 对数器优化：使用 Random 类替代 Math.random() 提升效率

2026-07-18

• 完成入门部分：复杂度、基础排序算法（选择、冒泡、插入）、二分查找

---

持续更新中...