algorithm - 我不明白稳定的算法定义

Question

在计算机科学中，稳定的排序算法会保留具有相同键的记录的顺序。

我只是不明白为什么某些排序算法是稳定的，而其他的则没有。基本排序算法对 int 数组的项目进行排序。如果我创建一个类或结构并使用相同的算法考虑交换整个对象，并选择按键排序，o 按年龄 ecc，那么每个算法都可以保留记录的顺序！

我想我错过了一些关于定义的东西。

非常感谢。

Answer 1

假设您有一个如下所示的数组：

a = [5, 4, 2a, 2b, 1]

其中aandb只是用来表示第一个 2 ( 2a) 在第二个 2 ( 2b) 之前。在稳定的排序算法中，结果将是：

a_stable = [1, 2a, 2b, 4, 5]

也就是说，元素的相对顺序没有改变 -2a在2b原始数组中出现，并且在排序数组中保持不变。

使用不稳定的算法，结果可能是：

a_nonstable = [1, 2b, 2a, 4, 5]

这仍然是正确排序的，只是相对于它们在原始未排序数组中的位置现在已经改变。