什么是排序算法中的稳定性?为什么它很重要?

稳定性之所以重要，有几个原因。一个是，如果两个记录不需要交换，交换它们可能会导致内存更新，一个页面被标记为脏，并且需要重新写入磁盘(或其他慢介质)。

这取决于你做什么。

假设您有一些具有姓和名字段的人员记录。首先按名字排序。如果使用稳定的算法按姓氏对列表进行排序，那么您将得到一个按姓和名排序的列表。

稳定排序总是在相同的输入上返回相同的解(排列)。

例如，[2,1,2]将使用稳定排序作为排列[2,1,3](第一个是索引2，然后是索引1，然后是索引3)，这意味着输出总是以相同的方式洗牌。其他不稳定，但仍然正确的排列是[2,3,1]。

快速排序是不稳定的排序，同一元素之间的排列差异取决于选取枢轴的算法。有些实现是随机的，可以快速排序，使用相同的算法对相同的输入产生不同的排列。

稳定排序算法具有一定的确定性。

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

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

peach
straw
apple
spork

如果我们只根据每个单词的首字母对列表进行排序，那么稳定排序将产生:

apple
peach
straw
spork

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

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

你不能以同样的方式堆叠不稳定的类型。

排序稳定性是指具有相同键的记录在排序前后保持相对顺序。

因此，当且仅当你要解决的问题需要保持相对顺序时，稳定性才重要。

如果你不需要稳定性，你可以从库中使用一个快速的、占用内存的算法，比如堆排序或快速排序，然后忘记它。

如果你需要稳定，那就更复杂了。稳定算法比不稳定算法具有更高的大o CPU和/或内存使用量。所以当你有一个大的数据集时，你必须在CPU和内存之间做出选择。如果CPU和内存都受到限制，就有问题了。一种较好的折衷稳定算法是二叉树排序;维基百科的文章有一个基于STL的简单得可怜的c++实现。

通过添加原始记录号作为每条记录的最后位置键，可以将不稳定的算法变为稳定的算法。

如果你假设你正在排序的只是数字，并且只有它们的值才能识别/区分它们(例如，具有相同值的元素是相同的)，那么排序的稳定性问题是没有意义的。

然而，排序中具有相同优先级的对象可能是不同的，有时它们的相对顺序是有意义的信息。在这种情况下，不稳定排序会产生问题。

当然，你也可以尝试着将配对值[T,L]映射到一个实数[R]，然后根据[R]值对所有玩家进行排序。

然而，如果稳定排序是可行的，那么你可以简单地按照[T](更快的玩家优先)和[L]对整个列表进行排序。在这种情况下，玩家的相对顺序(根据时间成本)不会在你根据他们清理的迷宫级别对他们进行分组后发生改变。

PS:当然，对特定问题进行两次排序的方法并不是最好的解决方案，但对于解释海报的问题来说，这应该足够了。

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

然而，任何给定的不稳定排序算法都可以被修改为稳定排序算法。可以有排序算法特定的方法使其稳定，但一般来说，任何基于比较的排序算法本质上不稳定，都可以通过改变键比较操作来修改为稳定，以便两个键的比较将位置作为具有相同键的对象的一个因素。

一种稳定排序算法是将相同的元素按照它们在输入中出现的相同顺序排序的元素，而不稳定的排序可能不满足这种情况。——_{我感谢我的算法讲师Didem Gozupek提供了关于算法的见解} < / >吃饭。

我再次需要编辑这个问题，因为有些人没有理解演讲的逻辑。另一方面，你可以考虑由键值对组成的图示。

稳定排序算法:

• 插入排序
• 归并排序
• 冒泡排序
• 蒂姆排序
• 计数排序
• 块排序
• Quadsort
• 图书馆分类
• 鸡尾酒摇酒器
• Gnome排序
• 奇偶排序

不稳定排序算法:

• 堆排序
• 选择排序
• 壳类
• 快速排序
• Introsort(受制于快速排序)
• 树的种类
• 循环排序
• Smoothsort
• 比赛排序(以Hesapsort为准)

我知道这个问题有很多答案，但对我来说，这个答案，通过罗伯特。哈维。，总结得更清楚:

稳定排序是一种保留输入集原始顺序的排序，其中[不稳定]算法不区分两个或多个项。

< a href = " https://softwareengineering.stackexchange.com/a/247441/298955 " > < / >来源

下面是更多想要稳定类型的原因的例子。数据库就是一个常见的例子。以交易数据库为例，其中包括最后一个|的名字，日期|的购买时间，项目编号，价格。假设数据库通常按日期|时间排序。然后进行查询，根据最后的|名字对数据库进行排序，因为稳定排序保留原始顺序，即使查询比较只涉及最后的|名字，每个最后|名字的事务将按照数据|时间顺序进行。

一个类似的例子是经典的Excel，它一次只能对3列进行排序。要对6列进行排序，首先对最低有效度的3列进行排序，然后对最高有效度的3列进行排序。

稳定基数排序的一个经典示例是卡片排序器，用于按以10为基数的数字列进行排序。卡片从最低有效数字到最高有效数字排序。在每一次传递中，读取一副牌，并根据该列中的数字将其分为10个不同的箱子。然后将这10箱卡片按顺序放回输入料斗(“0”卡片先，“9”卡片最后)。然后对下一列进行另一遍，直到所有列都被排序。实际的卡片分类器有超过10个箱子，因为一张卡片上有12个区域，一列可以是空白的，还有一个读错的箱子。要对字母进行排序，每列需要进行2次传递，第一次传递数字，第二次传递12 11区域。

后来(1937年)出现了卡片整理(合并)机，可以通过比较字段来合并两副牌。输入是两副已经排序的牌，一副主牌和一副更新牌。整理器将两个甲板合并为一个新的主箱和一个存档箱，存档箱可选地用于主副本，以便新的主箱在出现副本时只有更新卡。这可能是最初(自底向上)归并排序背后思想的基础。