1. 方法
冒泡,插入,选择,快排,归并,堆排,桶排,计数,基数。
其中,选择、快排、堆排是不稳定的,其他都是稳定的。
2. 时间复杂度
复杂度 | 平均 | 最好 | 最差 | 稳定性 |
---|---|---|---|---|
快排 | nlog2n | - | n2 | 不稳 |
冒泡 | n2 | n | - | 稳定 |
插入 | n2 | n | - | 稳定 |
选择 | n2 | - | - | 不稳 |
堆排 | nlog2n | - | - | 不稳 |
归并 | nlog2n | - | - | 稳定 |
另外,桶排、计数、基数,平均复杂度为O(n),其中,计数排序最差复杂度也为O(n)。
3. 应用
冒泡排序:站队时高矮个排序、小规模数据排序(4个数字排序,手动冒泡),初学者讲解for循环使用。
网友评论