排序算法学习与实践仓库

本项目为个人学习排序算法的实践代码与总结文档，包含多种经典排序算法的Java实现、性能测试及核心思想分析。

📂 项目结构

sort_study/
├── src/
│ └── main/
│ └── java/
│ ├── com/
│ │ └── benjamin/
│ │ ├── heap/
│ │ │ └── BigRootHeap.java # 大根堆实现
│ │ ├── sorter/
│ │ │ ├── impl/ # 排序算法实现
│ │ │ │ ├── BubbleSort.java
│ │ │ │ ├── HeapSort.java
│ │ │ │ ├── InsertionSort.java
│ │ │ │ ├── MergeSort.java
│ │ │ │ ├── QuickSort.java
│ │ │ │ └── SelectionSort.java
│ │ │ └── Sort.java # 排序接口
│ │ ├── misc/
│ │ │ ├── ArrayGenerator.java # 数组生成器
│ │ │ └── Print.java # 打印工具类
│ │ └── HeapSortDemo.java # 堆排序示例

🚀 实现算法

1. 冒泡排序 (BubbleSort)

核心思想：通过相邻元素比较交换，使最大元素逐渐"浮"到数组末端
特点：

• 稳定排序
• 原地排序（O(1)空间复杂度）
• 时间复杂度：O(n²)

2. 插入排序 (InsertionSort)

核心思想：将未排序元素逐个插入已排序序列的合适位置
适用场景：

• 小规模数据
• 近乎有序的数据集
• 时间复杂度：O(n²)（最坏） / O(n)（最好）

3. 选择排序 (SelectionSort)

实现逻辑：每次循环选择最小元素放到已排序序列末尾
特点：

• 非稳定排序
• 比较次数固定为O(n²)
• 交换次数O(n)

4. 归并排序 (MergeSort)

分治策略：

1. 递归拆分数组至单个元素
2. 合并有序子数组
   优势：

• 稳定排序
• 时间复杂度稳定O(n log n)
• 需要O(n)额外空间

5. 快速排序 (QuickSort)

核心操作：

1. 选取基准值(pivot)
2. 分区操作(partition)
3. 递归处理子数组
   优化点：

• 三数取中法选择pivot
• 小数组切换插入排序
• 时间复杂度：O(n log n)（平均）

6. 堆排序 (HeapSort)

实现步骤：

1. 构建大根堆
2. 交换堆顶与末尾元素
3. 调整堆结构
   特点：

• 原地排序
• 时间复杂度O(n log n)
• 不稳定排序

📊 复杂度对比

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
插入排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定

🛠 使用说明

1. 克隆仓库：

git clone https://github.com/fatbun/sort_study.git


运行示例（如HeapSortDemo）：
// 查看具体排序类的main方法

📚 学习资源

《算法（第4版）》《数据结构与算法分析：Java语言描述》VisuAlgo算法可视化平台
欢迎通过Issue提交改进建议，共同完善排序算法知识体系！

可根据实际实现细节补充以下内容：
1. 添加各算法的代码片段示例
2. 补充性能测试对比数据
3. 增加算法可视化示意图
4. 添加具体使用示例（如输入输出示例）
5. 补充不同数据规模下的表现分析