Skip to content

feat: add quick sort algorithm

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

Closes #9 (closed) - add-quicksort-algorithm

更改内容

  • 在 sort.py 中实现了快速排序算法
  • 使用三数取中法选择pivot,避免在有序数组上的最坏情况
  • 在 test_sort.py 中添加了完整的测试覆盖和算法元数据
  • 在 main.py 中集成了快速排序演示
  • 所有测试通过 (50/50)

算法特性

  • 时间复杂度: 平均 O(n log n), 最坏 O(n²)
  • 空间复杂度: O(log n)
  • 稳定性: 否
  • 适用场景: 通用排序,性能优秀

测试结果

所有50个测试通过 快速排序在所有测试用例上正常工作 性能测试通过(1000元素逆序数组)

技术实现

  • 使用median-of-three pivot选择策略
  • 递归实现,空间复杂度为O(log n)
  • 处理边界情况(空数组、单元素数组)
  • 与现有测试框架完全兼容

Merge request reports