安卓技术-排序算法
2020-02-16 本文已影响0人
七色瑾林
1. 方法
冒泡，插入，选择，快排，归并，堆排，桶排，计数，基数。
其中，选择、快排、堆排是不稳定的，其他都是稳定的。
2. 时间复杂度
| 复杂度 | 平均 | 最好 | 最差 | 稳定性 |
|---|---|---|---|---|
| 快排 | nlog2n | - | n2 | 不稳 |
| 冒泡 | n2 | n | - | 稳定 |
| 插入 | n2 | n | - | 稳定 |
| 选择 | n2 | - | - | 不稳 |
| 堆排 | nlog2n | - | - | 不稳 |
| 归并 | nlog2n | - | - | 稳定 |
另外，桶排、计数、基数，平均复杂度为O(n),其中，计数排序最差复杂度也为O(n)。
3. 应用
冒泡排序：站队时高矮个排序、小规模数据排序（4个数字排序，手动冒泡），初学者讲解for循环使用。
