InTheBloodHorse

数据结构与算法(3) 稳定排序与非稳定排序

字数统计: 247阅读时长: 1 min
2018/09/18 Share

图解

TIM截图20180918131703.jpg

解释

顾名思义,稳定排序是稳定的,具体什么是稳定的,那就是index,也就是位置的是稳定,比如在两个值相同的情况下,排序之后的顺序还是不变

哪些是稳定的?哪些不是

稳定排序

冒泡排序和归并排序是稳定的

非稳定排序

快速排序和选择排序是非稳定的

应用,什么时候需要在乎是否稳定

在排序学生成绩的时候,假如两个学生成绩相同,那么肯定是学号小的在前面,这就是一个经典的应用。
还有就是之前提到的加权随机算法假如我们选择排序的方案,先进行排序,假如成员A,B权重相同,那么顺序就很重要了,所以我们可以让注册时间早的排在前面(当然这个第二关键字很多,这里不一一举例)

CATALOG
  1. 1. 图解
  2. 2. 解释
  3. 3. 哪些是稳定的?哪些不是
    1. 3.1. 稳定排序
    2. 3.2. 非稳定排序
  4. 4. 应用,什么时候需要在乎是否稳定