数据结构(python) —— 【15: NB三人组小结】
快速、堆、归并排序小结
之前讲了Low B三人组，然后最近又讲了NB三人组的快速排序、堆排序和归并排序。
数据结构(python) —— 【08排序: 快速排序】
数据结构(python) —— 【11: 堆排序】
数据结构(python) —— 【14: 归并排序】
其中堆排序可能比较难理解，需要花费更多时间去结合图文进行理解。今天来把这三个排序进行小结一下。
三种排序算法的时间复杂度都是O(nlog(n))
一般情况下，就运行时间而言:
快速排序 < 归并排序 < 堆排序
三种排序算法的缺点:
快速排序: 极端情况下，排序效率低
归并排序: 需要额外的内存开销
堆排序: 在快的排序算法中较慢
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 代码复杂度 | ||
| 最坏情况 | 平均情况 | 最好情况 | ||||
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 | 简单 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | 简单 |
| 插入排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 | 简单 |
| 快速排序 | O(n^2) | O(nlogn) | O(nlogn) | 平均情况O(logn);最坏情况O(n) | 不稳定 | 较复杂 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 复杂 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 |