Skip to content

feat: 实现快速排序算法 (Quick Sort)

Yun.Long requested to merge feature/33-task into main

变更内容

为项目新增快速排序（Quick Sort）算法实现，独立基于 main 分支开发。

修改文件

  • sort.py: 新增 quick_sort 函数，迭代式实现 + median-of-three 选轴
  • test_sort.py: 注册 quick_sort 到 SORT_FUNCTIONS 列表，补充 ALGO_INFO 元数据
  • main.py: 在演示循环中加入 Quick Sort
  • README.md: 更新算法对比表格，新增 Quick Sort 一行

针对 Issue 要求的关键设计

Issue 特别提到「不要因为数据太多、递归层数过深导致 stackoverflow」：

  1. 迭代式实现：用显式 stack: list[tuple[int, int]] 替代递归调用，彻底绕过 Python 默认 1000 层递归限制
  2. 小分区优先处理：较大分区先压栈，保证栈深度始终为 O(log n)

算法特性

项目 值
时间复杂度（平均） O(n log n)
时间复杂度（最坏） O(n²)
空间复杂度 O(1)
稳定性 不稳定

测试结果

全部 50 个测试用例通过 ✅

Closes #33

Merge request reports