常用排序算法对比
相关术语解释:文章来源地址https://www.toymoban.com/news/detail-619127.html
- 稳定:如果 a 原本在 b 前面,而 a = b,排序之后 a 仍然在 b 的前面。
- 不稳定: 如果 a 原本在 b 前面,而 a = b,排序之后 a 可能出现在 b 的后面。
- 内排序:所有排序操作都在内存中完成。
- 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行。
- 时间复杂度:一个算法执行所耗费的时间。
- 空间复杂度:运行完一个程序所需内存的大小。
- n:数据规模。
- k:“桶”的个数。
- In-place:不占用额外内存。
- Out-place:占用额外内存。
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | In-place | 稳定 |
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | In-place | 不稳定 |
插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | In-place | 稳定 |
希尔排序 | O(n log n) | O(n log 2(n)) | O(n log 2(n)) | O(1) | In-place | 不稳定 |
归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | Out-place | 稳定 |
快速排序 | O(n log n) | O(n log n) | O(n^2) | O(log (n)) | In-place | 不稳定 |
堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不稳定 |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | Out-place | 稳定 |
桶排序 | O(n + k) | O(n + k) | O(n^2) | O(n + k) | Out-place | 稳定 |
基数排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | Out-place | 稳定 |
文章来源:https://www.toymoban.com/news/detail-619127.html
到了这里,关于【数据结构与算法】常用排序算法对比的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!