本文共 517 字,大约阅读时间需要 1 分钟。
之前讲了Low B三人组,然后最近又讲了NB三人组的快速排序、堆排序和归并排序。
其中堆排序可能比较难理解,需要花费更多时间去结合图文进行理解。今天来把这三个排序进行小结一下。 三种排序算法的时间复杂度都是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) | 稳定 | 较复杂 |
转载地址:http://zbiwi.baihongyu.com/