Skip to content

README.md

Latest commit

 

History

History
110 lines (95 loc) · 3.55 KB

README.md

File metadata and controls

110 lines (95 loc) · 3.55 KB
Raw

排序算法学习与实践仓库

本项目为个人学习排序算法的实践代码与总结文档，包含多种经典排序算法的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. 补充不同数据规模下的表现分析