排序算法的稳定性指的是经过排序后,大小相同的元素顺序是否发生改变。这一属性有时十分重要,比如,对于一个列车时刻表,我们首先将其按出发时间排序,之后再一次按照编号排序时,我们希望最大程度上保留之前的时间顺序。
几种常见排序算法稳定性:
1 选择排序:稳定
在选择排序中,两个相同元素不会发生交换,因为选择各元素的顺序依照原顺序
2 插入排序:不稳定
如果一个元素需要进行多次交换才能到达其正确位置,其沿途的相同元素顺序会被颠倒
3 希尔排序:不稳定
希尔排序就是插入排序升级版,所有原因和插入排序一样
4 归并排序:稳定
归并排序的merge方法也是按照原数组顺序组合元素,不会发生相同元素位置变化