排序的稳定性

排序的稳定性

稳定性的定义

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

稳定性的意义

  • 如果一组数据只需要一次排序,则稳定性一般是没有意义的,如果一组数据需要多次排序,稳定性是有意义的。例如要排序的内容是一组商品对象,第一次排序按照价格由低到高排序,第二次排序按照销量由高到低排序,如果第二次排序使用稳定性算法,就可以使得相同销量的对象依旧保持着价格高低的顺序展现,只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义,而且可以减少系统开销。

  • 第一次按照价格从低到高排序:

    商品名称 价格 销量
    三星Note9 3999 21
    华为mate30 4999 65
    华为p30 5999 65
    Iphone 11 6899 32
  • 第二次按照销量进行从高到低排序:

    商品名称 价格 销量
    华为mate30 4999 65
    华为p30 5999 65
    Iphone 11 6899 32
    三星Note9 3999 21

常见排序算法的稳定性:

  • 冒泡排序

    • 只有当arr[i]>arr[i+1]的时候,才会交换元素的位置,而相等的时候并不交换位置,所以冒泡排序是一种稳定排序算法。
  • 选择排序:

    • 选择排序是给每个位置选择当前元素最小的,例如有数据{5(1),8 ,5(2), 2, 9 },第一遍选择到的最小元素为2,所以5(1)会和2进行交换位置,此时5(1)到了5(2)后面,破坏了稳定性,所以选择排序是一种不稳定的排序算法。
  • 插入排序

    • 比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么把要插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
  • 希尔排序

    • 希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。
  • 归并排序

    • 归并排序在归并的过程中,只有arr[i]<arr[i+1]的时候才会交换位置,如果两个元素相等则不会交换位置,所以它并不会破坏稳定性,归并排序是稳定的。
  • 快速排序

    • 快速排序需要一个基准值,在基准值的右侧找一个比基准值小的元素,在基准值的左侧找一个比基准值大的元素,然后交换这两个元素,此时会破坏稳定性,所以快速排序是一种不稳定的算法。
原文地址:https://www.cnblogs.com/momo-88/p/13434038.html