| 冒泡 |
O
(
n
2
)
O(n^2)
O(n2) |
O
(
n
)
O(n)
O(n) |
O
(
n
2
)
O(n^2)
O(n2) | O(1) | 稳定 | In-place | 对于8万个元素的数列，用时16秒 | n小较好 |
| 选择 |
O
(
n
2
)
O(n^2)
O(n2) |
O
(
n
2
)
O(n^2)
O(n2) |
O
(
n
2
)
O(n^2)
O(n2) | O(1) | 不稳定 | In-place | 对于8万个元素的数列，用时3秒 | n小较好 |
| 插入 |
O
(
n
2
)
O(n^2)
O(n2) |
O
(
n
)
O(n)
O(n) |
O
(
n
2
)
O(n^2)
O(n2) | O(1) | 稳定 | In-place | 对于8万个元素的数列，用时5秒 | 大部分已排序时较好 |
| 希尔Shell |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) | |
O
(
n
s
)
O(n^s)
O(ns) 1 < s < 2 | O(1) | 不稳定 | In-place | 交换法对于8万个元素的数列，用时16秒；移动法对于8万个元素的数列，用时1秒 | s是所选分组 |
| 快速 |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) |
O
(
n
2
)
O(n^2)
O(n2) |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) | 不稳定 | In-place | 对于8万个元素的数列，用时不到1秒；80万个元素的数列，用时1秒 | n大较好 |
| 归并 |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) | O(1) | 稳定 | Out-place | 对于8万个元素的数列，用时不到1秒；80万个元素的数列，用时1秒 | n大较好 |
| 基数 |
O
(
l
o
g
R
B
)
O(log_RB)
O(logR?B) | |
O
(
l
o
g
R
B
)
O(log_RB)
O(logR?B) | O(n) | 稳定 | Out-place | 对于80万个元素的数列，用时不到1秒；800万个元素的数列，用时1秒；8000万个元素的数列，直接内存溢出 | B是真数(0-9)，R是基数(个十百) |
| 堆 |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) | O(1) | 不稳定 | In-place | 800万个元素的数列，用时3秒 | n大较好 |
| 交换 |
O
(
n
2
)
O(n^2)
O(n2) | |
O
(
n
2
)
O(n^2)
O(n2) | O(1) | 不稳定 | | | n小较好 |