| 排序方法 | 平均时间复杂度 | 最坏情况时间下时间复杂度 | 额外空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 简单选择排序 | O(N2) | O(N2) | O(1) | 不稳定 |
| 冒泡排序 | O(N2) | O(N2) | O(1) | 稳定 |
| 直接插入排序 | O(N2) | O(N2) | O(1) | 稳定 |
| 希尔排序 | O(Nd) | O(N2) | O(1) | 不稳定 |
| 堆排序 | O(NlogN) | O(NlogN) | O(1) | 不稳定 |
| 快速排序 | O(NlogN) | O(N2) | O(logN) | 不稳定 |
| 归并排序 | O(NlogN) | O(NlogN) | O(N) | 稳定 |
| 基数排序 | O(P(N+B)) | O(P(N+B)) | O(N+B) | 稳定 |
来源: 中国大学MOOC数据结构 陈越、何钦铭
注: 希尔排序中d取决于增量的选取，其可能小于2
基数排序中，B代表有多少个桶，P为收集的趟数
