| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 备注 |
|---|
| 冒泡排序 (Bubble Sort) | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 实现简单，可提前结束 |
| 选择排序 (Selection Sort) | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 交换次数最少 |
| 插入排序 (Insertion Sort) | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 小规模数据表现优秀 |
| 希尔排序 (Shell Sort) | O(n log n)~O(n²) | O(n log n) | O(n²) | O(1) | 不稳定 | 插入排序优化版 |
| 归并排序 (Merge Sort) | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 分治思想，链表排序常用 |
| 快速排序 (Quick Sort) | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | 面试出现频率最高 |
| 堆排序 (Heap Sort) | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 适合TopK问题 |
| 计数排序 (Counting Sort) | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 | 适合整数范围较小 |
| 桶排序 (Bucket Sort) | O(n+k) | O(n+k) | O(n²) | O(n+k) | 视实现而定 | 数据分布均匀时效果好 |
| 基数排序 (Radix Sort) | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 | 按位排序 |
Reply by Email