| 最好 | 最坏 | 平均 | 是否原地算法？ | 是否稳定？ | |
|---|---|---|---|---|---|
| 冒泡排序 | \( n \) |
\( n^2 \) |
\( n^2 \) |
√ | √ |
| 插入排序 | \( n \) |
\( n^2 \) |
\( n^2 \) |
√ | √ |
| 选择排序 | \( n^2 \) |
\( n^2 \) |
\( n^2 \) |
√ | × |
时间复杂度
- 有序度：数列中具有有序关系的元素对的个数
- 逆序度：数列中有序关系颠倒的元素对的个数
- 满有序度 = 有序度 + 逆序度 =
\( \frac{n*(n-1)}{2} \) - 平均有序度 = (有序度 + 逆序度) / 2 =
\( \frac{n*(n-1)}{4} \)
数列的逆序度即为冒泡排序和插入排序每次最少交换元素的次数。