各种排序算法比较
类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | ||
---|---|---|---|---|---|---|
平均情况 | 最好情况 | 最坏情况 | 辅助空间 | |||
插入排序 | 直接插入 | 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代表关键字的个数。