本文共 1005 字，大约阅读时间需要 3 分钟。
一、常见问题
1、什么是稳定性？哪些排序算法是稳定排序？
稳定性，大概就是能保证排序前后，两个相等的数在序列中的相对次序不变，即，排序前A在A'前面，排序后A依然在A'前面。
稳定的排序有：冒泡排序（每次比较相邻两个元素，当前者比后者大时交换，当两者相等时不交换）、插入排序（如果已排序部分的当前元素比待插入元素大才右移，相等则不右移）、归并排序（底层基于合并操作，而合并操作不改变相同元素的先后顺序）、
不稳定的排序有：选择排序（5,8,5,2,9经过一轮排序之后，两个5的先后顺序发生了变化）、希尔排序（相同的元素可能被分配到各自的组中进行插入排序，在插入排序中的移动有可能导致其先后顺序发生改变）、快速排序（）
2、初始排列顺序对算法的影响
算法复杂度与初始状态无关的有：选择排序、堆排序、归并排序、基数排序
元素总比较次数与初始状态无关的有：选择排序、基数排序
元素总移动次数与初始状态无关的有：归并排序、基数排序
3、小结
| 算法 | 稳定性 | 时间复杂度（平均、最好、最坏） | 空间复杂度 | 排序方式 | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | √ | 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) O(n^2) | O(1) | In-place | 时间复杂度和初始顺序有关，因此通常处理一个基本有序的序列 |
| 希尔排序 | × | O(nlogn) O(n(logn)^2) O(n(logn)^2) | 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 | |
| 三向切分快速排序 | × | N ~ NlogN | O(logn) | 适用于有大量重复主键 | |
| 堆排序 | × | O(nlogn) O(nlogn) O(nlogn) | O(1) | In-place | 无法利用局部性原理 |
| 计数排序 | √ | O(n+k) O(n+k) O(n+k) | O(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(n+k) | Out-place |
转载地址：http://gfnii.baihongyu.com/