热门标签
热门文章
当前位置: article > 正文
算法刷题1-10大排序算法汇总
作者：人工智能uu | 2024-07-06 10:32:49
赞
踩
算法刷题1-10大排序算法汇总
十种常见排序算法可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
| 排序方法 | 分类 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 | 重要程度 |
| 冒泡排序 | 比较类-交换排序 | O(n*2) | O(n*2) | O(n) | O(1) | 稳定 | |
| 快速排序 | 比较类-交换排序 | O(nlogN) | O(n*2) | O(nlogN) | O(nlogN) | 不稳定 | |
| 简单插入排序 | 比较类-插入排序 | O(n*2) | O(n*2) | O(n) | O(1) | 稳定 | |
| 希尔排序 | 比较类-插入排序 | O(n*1.3) | O(n*2) | O(n) | O(1) | 不稳定 | |
| 简单选择排序 | 比较类-选择排序 | O(n*2) | O(n*2) | O(n*2) | O(1) | 不稳定 | |
| 堆排序 | 比较类-选择排序 | O(nlogN) | O(nlogN) | O(nlogN) | O(1) | 不稳定 | |
| 归并排序 | 比较类-归并排序 | O(nlogN) | O(nlogN) | O(nlogN) | O(n) | 稳定 | |
| 计数排序 | 非比较类 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 | |
| 桶排序 | 非比较类 | O(n+k) | O(n**2) | O(n) | O(n+k) | 稳定 | |
| 基数排序 | 非比较类 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
指标解释：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
参考：
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/792603
推荐阅读
相关标签
