algorithm - 什么是排序算法的稳定性，为什么它很重要？

Question

我很好奇，为什么稳定性在排序算法中重要或不重要？

Answer 1

如果具有相同键的两个对象出现在排序输出中的顺序与它们出现在要排序的输入数组中的顺序相同，则称排序算法是稳定的。有些排序算法本质上是稳定的，如插入排序、归并排序、冒泡排序等，而有些排序算法则不稳定，如堆排序、快速排序等。

背景:“稳定”排序算法使具有相同排序键的项目按顺序排列。假设我们有一个包含 5 个字母的单词列表:

peach
straw
apple
spork

如果我们仅按每个单词的第一个字母对列表进行排序，那么稳定排序会产生:

apple
peach
straw
spork

在不稳定排序算法中，straw 或spork 可以互换，但在稳定算法中，它们保持相同的相对位置(也就是说，由于 straw 在输入中出现在 spork 之前，所以它在输出中也出现在 spork 之前)。

我们可以使用此算法对单词列表进行排序:按第 5 列稳定排序，然后是第 4 列，然后是第 3 列，然后是第 2 列，然后是第 1 列。最后，它会被正确排序。说服自己。 (顺便说一句，该算法称为基数排序)

现在回答您的问题，假设我们有一个名字和姓氏列表。我们被要求“按姓氏，然后按名字”排序。我们可以先按名字排序(稳定或不稳定)，然后按姓氏排序。在这些排序之后，列表主要按姓氏排序。但是，如果姓氏相同，则按名字排序。

您不能以相同的方式堆叠不稳定的排序。