| 算法 | 平均复杂度 | 最坏情况复杂度 | 最好情况复杂度 | 稳定性 | 其他 |
|---|---|---|---|---|---|
| 冒泡 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | 稳定 | |
| 选择 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | 不稳定 | 性能与初始状态无关 |
| 直接插入 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | 稳定 | |
| 折半插入 | $O(n^2)$ | $O(n^2)$ | $O(n\log n)$ | 稳定 | |
| 希尔 | $O(n^2)$ | $O(n\log n)$ | 不稳定 | 需要选择步长 | |
| 快速 | $O(n\log n)$ | $O(n^2)$ | $O(n\log n)$ | 不稳定 | 对于有序序列性能变差 |
| 锦标赛 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | 稳定 | 大量附加存储 |
| 堆 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | 不稳定 | 原地操作 |
| 归并 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | 稳定 | $O(n)$附加空间 |
有限取值的序列：计数排序：$O(n)$
取值有范围的序列：箱排序：$O(n)$
排序关键字分解：基数排序：$O(nd)$
如果排序对象数量巨大，无法全部调入内存，则需要进行外部排序。
归并排序是用于实现外部排序的主要策略