我在 Python 中实现了所有排序算法——而 Python 的内置排序轻松击败了它们全部
发布: (2026年2月5日 GMT+8 14:13)
3 min read
原文: Dev.to
Source: Dev.to
基准结果
| 算法 | 100 个元素 | 1,000 个元素 | 5,000 个元素 | 实际限制 |
|---|---|---|---|---|
| Bubble Sort | 0.001 s | 0.15 s | 3.2 s | ~500 个元素 |
| Selection Sort | 0.001 s | 0.13 s | 2.8 s | ~500 个元素 |
| Insertion Sort | 0.0005 s | 0.08 s | 1.9 s | ~1,000（在几乎已排序的情况下表现极佳！） |
| Merge Sort | 0.002 s | 0.025 s | 0.14 s | 可用但较慢 |
| Quick Sort | 0.002 s | 0.021 s | 0.11 s | 可用，但递归会带来性能损失 |
| Heap Sort | 0.002 s | 0.029 s | 0.16 s | 稳定可靠，却从未赢过 |
sorted() (Timsort) | 0.0003 s | 0.0045 s | 0.025 s | 始终使用它 |
关键要点
- 插入排序 在极小规模的输入上胜过归并/快速排序；Python 的函数调用代价高：它们涉及方法分派和类型检查，而不是单条 CPU 指令。
- 递归开销使得快速排序的函数调用变得昂贵。
- 内存分配：归并排序会创建成千上万的临时列表，导致垃圾回收暂停。
- Timsort 是一种混合型的天才算法：它会检测已有的有序段，对小块使用插入排序，并自适应地进行合并，全部在经过优化的 C 代码中实现。
插入排序示例
def insertion_sort(arr):
"""Return a sorted copy of *arr* using insertion sort."""
arr = arr.copy()
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr切勿在生产环境的 Python 中自行实现排序。
使用sorted()或list.sort()—— 它们更快、更稳定、且经过实战检验。仅在学习或极少数特殊场景下才自行编写。
更多资源
- 详细解释 – (link to the full article)
- 全部源码 – (link to the repository)
- 基准脚本 – (link to the script)
- 原始基准数据 – (link to the data)
外部链接
- 完整博客文章：
- GitHub 仓库：
Python 的排序性能让你最惊讶的是什么？
欢迎在评论区分享你的想法。