# 排序算法的总结
---

In-place 就是常数内存

Out-place 就是额外内存

| 排序算法 | 平均时间复杂度 | 最好情况 |最坏情况 |空间时间复杂度 |排序方式 |稳定性 |
| -------- | -------- | -------- | -------- | -------- | -------- |-------- |
| 冒泡排序 | O(n^2) | O(n) |O(n^2) | O(1) | In-place |稳定 |
| 选择排序 | O(n^2) | O(n^2) |O(n^2) | O(1) | In-place |不稳定 |
| 插入排序 | O(n^2) | O(n^2) |O(n^2) | O(1) | In-place |稳定 |
| 希尔排序 | O(nlogn) | O(nlog^2n) |O(nlog^2n) | O(1)| In-place |不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) |O(nlogn) | O(n) | Out-place |稳定 |
| 快速排序 | O(nlogn) | O(nlogn) |O(n^2) | O(logn) | In-place |不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) |O(nlogn) | O(1) | In-place |不稳定 |
| 基数排序 | O(n+k) | O(n+k) |O(n+k) | O(n+k) | Out-place |稳定 |
| 桶排序 | O(n+k) | O(n+k) |O(n^2) | O(n+k | Out-place |稳定 |
| 计数排序 | O(n+k) | O(n+k) |O(n+k) | O(k) | Out-place |稳定 |


###### tags: `排序算法`