常见排序算法的稳定性

定义

数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。

意义

比如手机有销量和价格，先对价格排序，再对销量排序，如果排序算法是稳定的，当两手机销量相同时，那么价格也会是有序的。

常见排序算法的稳定性

• 冒泡排序(稳定)

  

  如图所示的三个5, 他们的顺序在排序后顺序不会被打乱

• 选择排序 (不稳定)

  

  如图所示的三个5, 第一5会在排序后, 变成最后一个5

• 插入排序(稳定)

  

  如图所示的三个5, 他们的顺序在排序后顺序不会被打乱

• 希尔排序(不稳定)

  

  如图所示, 同一组中相同元素, 在一轮排序中顺序不会被打乱, 但是在不同组中的相同元素, 不能保证顺序不被打乱

• 归并排序(稳定)

  

  如图所示的三个5, 他们的顺序在排序后顺序不会被打乱

• 快速排序(不稳定)

  • 单边扫描

    

  • 两边扫描

    

  如图所示, 所示的两个5, 他们的顺序在排序后顺序会被打乱