Skip to content

feat: add quick sort algorithm

Yun.Long requested to merge feature/quick-sort into main

实现快速排序算法

Closes #16 (closed)

变更内容

  • ✅ 在 sort.py 中实现 quick_sort() 函数
  • ✅ 使用三数取中法（median-of-three）选择 pivot，优化性能
  • ✅ 添加辅助函数 _quick_sort_helper() 和 _partition()
  • ✅ 在 test_sort.py 中添加快速排序的测试和元信息
  • ✅ 在 main.py 中添加快速排序的演示
  • ✅ 更新 README.md 添加快速排序的复杂度信息

算法特性

  • 时间复杂度: 最优 O(n log n), 最坏 O(n²), 平均 O(n log n)
  • 空间复杂度: O(log n) (递归栈)
  • 稳定性: 不稳定
  • 优化: 使用三数取中法选择 pivot，避免在已排序数组上出现最坏情况

测试结果

✅ 所有 50 个测试通过

  • 7 种测试用例 × 5 种算法 = 35 个排序测试
  • 5 个不变性测试
  • 5 个元信息测试
  • 5 个性能测试

Merge request reports