| 类别 | 排序 | best | normal | worst | 辅助空间 | 稳定? | 比较次数 | 交换次数 |
|---|---|---|---|---|---|---|---|---|
| 插入 | 插入 | O(n) |
O(n 2 ) |
O(n 2 ) |
O(1) | 稳 | n-1,n(n-1)/2 | 0,n(n-1)/2 |
| 插入 | 希尔 | O(n) |
O(n 1.3 ) |
O(n 2 ) |
O(1) | 不稳 | ? | ? |
| 选择 | 选择 |
O(n 2 ) |
O(n 2 ) |
O(n 2 ) |
O(1) | 不稳 | n(n-1)/2 | 0,n-1 |
| 选择 | 堆 |
O(nlog 2 n) |
O(nlog 2 n) |
O(nlog 2 n) |
O(1) | 不稳 |
nlog 2 n |
? |
| 交换 | 冒泡 | O(n) |
O(n 2 ) |
O(n 2 ) |
O(1) | 稳 | n-1,n(n-1)/2 | 0,n(n-1)/2 |
| 交换 | 快速 |
O(nlog 2 n) |
O(nlog 2 n) |
O(n 2 ) |
O(nlog 2 n) |
不稳 |
nlog 2 n,n(n-1)/2 |
? |
| 归并 |
O(nlog 2 n) |
O(nlog 2 n) |
O(nlog 2 n) |
O(n) | 稳 |
nlog 2 n/2 |
? | |
| 基数 | O(d(rd+n)) | O(d(n+r)) | O(d(n+r)) | O(rd+n) | 稳 | ? | ? |
注：基数排序中d代表长度，r代表关键字基数，n代表关键字个数
版权声明：本文为weixin_43858318原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。