日期: 2019 年 9 月 29 日
学习内容: 排序算法的稳定性
笔记:
假设待排序序列中有若干个数值相同的元素, 使用某排序算法使序列有序, 如果在有序序列中数值相同的元素保持相对位置不变, 则称排序算法是稳定的, 反之, 称排序算法是不稳定的.
[5,4,3a,3b,3c,2,1] => [1,2,3a,3b,3c,4,5]
排序算法是否为稳定的是由具体算法决定的, 不稳定的算法在某种条件下可以变为稳定的算法, 而稳定的算法在某种条件下也可以变为不稳定的算法. 例如, 对于如下冒泡排序算法, 原本是稳定的排序算法, 如果将记录交换的条件改成 r[j]>=r[j+1], 则两个相等的记录就会交换位置, 从而变成不稳定的算法.
来源: http://www.bubuko.com/infodetail-3218493.html