常见排序算法的性能对比
| 时间复杂度 | 空间复杂度 | 可否实现稳定性 | |
|---|---|---|---|
| 选择 | (O(N^2)) | (O(1)) | No |
| 冒泡 | (O(N^2)) | (O(1)) | Yes |
| 插入 | (O(N^2)) | (O(1)) | Yes |
| 归并 | (O(Nlog N)) | (O(N)) | Yes |
| 快速 | (O(Nlog N)) | (O(log N)) | No |
| 堆 | (O(Nlog N)) | (O(1)) | No |
排序算法的稳定性
同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定 性的；否则就没有。
- 不具备稳定性的排序
- 选择排序、快速排序、堆排序
- 具备稳定性的排序
- 冒泡排序、插入排序、归并排序、一切桶排序思想下的排序
目前没有找到时间复杂度(O(N*logN))，额外空间复杂度(O(1))，又稳定的排序。