Skip to content

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

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

变更内容

为项目新增快速排序（Quick Sort）算法实现，针对 Issue #33 的要求，特别处理了递归栈溢出问题。

核心设计

  • 迭代式实现：使用显式栈（list）模拟递归调用，彻底避免 Python 递归深度限制导致的 RecursionError / stackoverflow
  • Median-of-Three 基准选取：取首、中、尾三元素的中位数作为 pivot，大幅降低遇到 O(n²) 最坏情况的概率
  • 小分区优先：每次将较大的分区先压栈，确保栈深度始终保持在 O(log n)

修改文件

  • sort.py：新增 quick_sort 函数（含 _median_of_three 和 _partition 内部辅助函数）
  • test_sort.py：注册 quick_sort 到 SORT_FUNCTIONS 列表，并补充 ALGO_INFO 元数据
  • main.py：在演示循环中加入 Quick Sort
  • README.md：更新算法对比表格，新增 Quick Sort 一行及说明注释

算法特性

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

* 采用 median-of-three pivot，实际最坏情况极难触发

测试结果

全部 60 个测试用例通过 ✅

Closes #33

Merge request reports