刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
面试题
Java版常用排序算法复杂度
使用微信搜索喵呜刷题，轻松应对面试！
答案：
分析&回答
算法复杂度分为时间复杂度和空间复杂度。其作用：
- 时间复杂度是指执行这个算法所需要的计算工作量；
- 空间复杂度是指执行这个算法所需要的内存空间；
时间和空间都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少；
| 排序算法 | 英文名称 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | Bubble | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
| 选择排序 | Selection | O(n²) | O(n²) | O(n²) | O(1) | In-place | 不稳定 |
| 插入排序 | Insertion | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
| 希尔排序 | Shell | O(n ㏒n) | O(n ㏒²n) | O(n ㏒²n) | O(1) | In-place | 不稳定 |
| 归并排序 | Merge | O(n ㏒n) | O(n ㏒n) | O(n ㏒n) | O(n) | Out-place | 稳定 |
| 快速排序 | Quick | O(n ㏒n) | O(n ㏒n) | O(n²) | O(㏒n) | In-place | 不稳定 |
| 堆排序 | Heap | O(n ㏒n) | O(n ㏒n) | O(n ㏒n) | O(1) | In-place | 不稳定 |
| 计数排序 | Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Out-place | 稳定 |
| 桶排序 | Bucket | O(n + k) | O(n + k) | O(n²) | O(n + k) | Out-place | 稳定 |
| 基数排序 | Radix | O(n × k) | O(n × k) | O(n × k) | O(n + k) | Out-place | 稳定 |
反思&扩展
特别关注快速排序、归并排序
O(x)是啥意思？
简单直观的 O(1) 、 O(n) 、O(log n) 复杂度说起
- O(1) 表示一次操作即可直接取得目标元素(比如字典或哈希表)，
- O(n) 意味着先要检查 n 个元素来搜索目标
- O(log n) 时间复杂度可能是在学二分搜索算法
创作类型：
原创
本文链接：Java版常用排序算法复杂度
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
