目录：
稳定性与复杂度
稳定性：指排序后，相同元素保持出现的先后顺序。
时间复杂度是O(N2)，额外空间负责度O(1)：
- l 冒泡排序：当遇到相同数时，该数不交换，将后面的数往下沉。可以稳定；
- l 插入排序：当遇到相同数时，该数不交换；可以稳定；
- l 选择排序：做不到稳定性。因为你要从后面的所有数中找到最小的，然后将前面的某一个a与该最值交换，如果有多个a存在，那么，a的先后顺序将无法保证。故做不到。
复杂度是O(N*logN)：
- l 归并排序：merge时，当相同时先拷贝左边（小区域）的数；可以稳定； 额外空间复杂度为O(N);
- l 快排：做不到稳定性； 额外空间复杂度为O(logN);
- l 堆排：做不到稳定性。在建大根堆的时候，就都已经不能保证稳定性了。 额外空间复杂度为O(1);
| 排序 |
稳定性 |
时间复杂度 |
额外空间复杂度 |
| 冒泡排序 |
稳定 |
O(N2) |
O(1) |
| 插入排序 |
稳定 |
O(N2) |
O(1) |
| 选择排序 |
不 |
O(N2) |
O(1) |
| 归并排序 |
稳定 |
O(N*logN) |
O(N) |
| 快排 |
不 |
O(N*logN) |
O(logN) |
| 堆排 |
不 |
O(N*logN) |
O(1) |
Over。。。
关于排序的总结（稳定性与复杂度）
原文：https://www.cnblogs.com/gjmhome/p/11482019.html
