各种排序算法比较
| 类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | ||
|---|---|---|---|---|---|---|
| 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | |||
| 插入排序 | 直接插入 | O($n^2$) | O($n$) | O($n^2$) | O($1$) | 稳定 |
| Shell排序 | O($n^{1.3}$) | O($n$) | O($n^2$) | O($1$) | 不稳定 | |
| 选择排序 | 直接选择 | O($n^2$) | O($n^2$) | O($n^2$) | O($1$) | 不稳定 |
| 堆排序 | O($n\log_{2}{n}$) | O($n\log_{2}{n}$) | O($n\log_{2}{n}$) | O($1$) | 不稳定 | |
| 交换排序 | 冒泡排序 | O($n^2$) | O($n$) | O($n^2$) | O($1$) | 稳定 |
| 快速排序 | O($n\log_{2}{n}$) | O($n\log_{2}{n}$) | O($n^2$) | O($n\log_{2}{n}$) | 不稳定 | |
| 归并排序 | O($n\log_{2}{n}$) | O($n\log_{2}{n}$) | O($n\log_{2}{n}$) | O($n$) | 稳定 | |
| 基数排序 | O($d(r+n)$) | O($d(n+rd)$) | O($d(r+n)$) | O($rd+n$) | 稳定 | |
Note:基数排序的复杂度中，r代表关键字的基数，d代表长度，n代表关键字的个数。
