排序的稳定性

排序的稳定性意味着排序算法是否保持结果输出中原始输入的等于键的相对顺序。

因此,如果具有相等键的两个对象在排序输出中以与输入未排序数组中出现的顺序相同的顺序出现,则称排序算法是稳定的。

考虑一对配对列表:

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

现在我们将使用每对的第一个元素对列表进行排序。

一个稳定的排序这份名单将输出以下列表:

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

因为 (9, 3) 也出现在原始列表中的 (9, 7) 之后。

一种不稳定的排序将输出以下列表:

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

不稳定排序可能会生成与稳定排序相同的输出,但并非总是如此。

着名的稳定种类:

众所周知的不稳定种类: