分析&回答
算法复杂度分为时间复杂度和空间复杂度。其作用：
- 时间复杂度是指执行这个算法所需要的计算工作量；
- 空间复杂度是指执行这个算法所需要的内存空间；
时间和空间都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少；
| 排序算法 | 英文名称 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | 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) 时间复杂度可能是在学二分搜索算法
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
