Skip to content

feat: add heap sort algorithm

Yun.Long requested to merge wip/add-heapsort-algorithm into main

Closes #10 (closed) - add-heapsort-algorithm

更改内容

  • 在 sort.py 中实现了堆排序算法,保证 O(n log n) 时间复杂度
  • 实现了 heapify() 和 build_max_heap() 辅助函数进行堆操作
  • 在 test_sort.py 中添加了完整的测试覆盖和算法元数据
  • 在 main.py 中集成了堆排序演示
  • 所有测试通过 (60/60)

算法特性

  • 时间复杂度: O(n log n) 最好、最坏、平均情况
  • 空间复杂度: O(1) 原地排序
  • 稳定性: 否
  • 适用场景: 需要保证最坏情况性能的场景

技术实现

  • 使用最大堆数据结构
  • 先构建最大堆,然后逐个提取最大元素
  • 原地排序,不需要额外空间
  • 性能稳定,不受输入数据分布影响

测试结果

所有60个测试通过 堆排序在所有测试用例上正常工作 性能测试通过(1000元素逆序数组) 输入数据不变性测试通过 算法元数据验证通过

Merge request reports