10 大排序算法
| 名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 额外空间复杂度 | 原地排序 | 稳定性 |
|---|
| 冒泡排序(Bubble Sort) | O(n) | O(n2) | O(n2) | O(1) | ✔ | ✔ |
| 选择排序(Selection Sort) | O(n2) | O(n2) | O(n2) | O(1) | ✔ | ❌ |
| 插入排序(Insertion Sort) | O(n) | O(n2) | O(n2) | O(1) | ✔ | ✔ |
| 归并排序(Merge Sort) | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ❌ | ✔ |
| 快速排序(Quick Sort) | O(nlogn) | O(n2) | O(nlogn) | O(logn) | ✔ | ❌ |
| 希尔排序(Shell Sort) | O(n) | O(n4/3) ~ O(n2) | 取决于步长序列 | O(1) | ✔ | ❌ |
| 堆排序(Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ✔ | ❌ |
| 计数排序(Counting Sort) | O(n + k) | O(n + k) | O(n + k) | O(n + k) | ❌ | ✔ |
| 基数排序(Radix Sort) | O(d ∗ (n + k)) | O(d ∗ (n + k)) | O(d ∗ (n + k)) | O(n + k) | ❌ | ✔ |
| 桶排序(Bucket Sort) | O(n + k) | O(n + k) | O(n + k) | O(n + m) | ❌ | ✔ |