以下是常见排序算法的时间复杂度对比表，包含了最优、平均和最坏情况下的时间复杂度：
| 排序算法 | 最优时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 希尔排序 | O(n log n) | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n + k) | 稳定 |
解释：
-
冒泡排序：
- 最优情况下是已经排序好的数组，时间复杂度为 𝑂(𝑛)O(n)。
- 平均和最坏情况下需要进行多次交换，时间复杂度为 𝑂(𝑛2)O(n2)。
- 稳定排序。
-
选择排序：
- 选择排序无论在什么情况下，都会扫描整个数组找到最小值进行交换，因此时间复杂度始终是 𝑂(𝑛2)O(n2)。
- 不稳定排序。
-
插入排序：
- 最优情况下（数组已经排好序），每次插入都只需要比较一次，时间复杂度为 𝑂(𝑛)O(n)。
- 最坏情况下需要进行 𝑂(𝑛2)O(n2) 次比较和交换。
- 稳定排序。
-
归并排序：
- 归并排序是一种分治算法，时间复杂度始终为 𝑂(𝑛log𝑛)O(nlogn)，无论输入数据如何。
- 稳定排序，但需要额外的空间 𝑂(𝑛)O(n)。
-
快速排序：
- 平均和最优情况下时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)。
- 最坏情况下（当数组已经是有序的或几乎有序时），时间复杂度为 𝑂(𝑛2)O(n2)，但通过随机化或三路切分可以优化。
- 不稳定排序。
-
堆排序：
- 时间复杂度始终为 𝑂(𝑛log𝑛)O(nlogn)，无论输入数据如何。
- 不稳定排序，适用于大规模数据的排序。
-
希尔排序：
- 通过选择不同的增量序列来改善插入排序的效率，最优情况下时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)，但具体性能取决于增量序列的选择。
- 最坏情况下可能达到 𝑂(𝑛2)O(n2)。
- 不稳定排序。
-
计数排序：
- 适用于整数范围较小的排序问题，时间复杂度为 𝑂(𝑛+𝑘)O(n+k)，其中 𝑘k 是数据范围。
- 空间复杂度为 𝑂(𝑘)O(k)，需要额外的空间来存储计数信息。
- 稳定排序。
-
桶排序：
- 时间复杂度通常为 𝑂(𝑛+𝑘)O(n+k)，其中 𝑘k 是桶的数量，适用于数据分布均匀的情况。
- 如果数据分布不均匀，最坏情况时间复杂度可能为 𝑂(𝑛2)O(n2)。
- 稳定排序。
-
基数排序：
- 适用于整数或固定长度字符串的排序，时间复杂度为 𝑂(𝑛𝑘)O(nk)，其中 𝑘k 是元素的最大位数。
- 稳定排序，适合处理范围较小的数据。
总结：
- 稳定性：稳定排序算法能够保持相同元素的相对顺序。例如，在多个元素值相同的情况下，排序前后这些元素的顺序不会改变。
- 时间复杂度：不同的排序算法在不同场景下有不同的效率表现。一般来说，对于大规模数据，选择 𝑂(𝑛log𝑛)O(nlogn) 复杂度的排序算法（如归并排序、快速排序、堆排序）会更合适。