387

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

4

10 回答 10

489

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

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

peach
straw
apple
spork

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

apple
peach
straw
spork

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

我们可以使用这个算法对单词列表进行排序：按第 5 列、第 4 列、第 3 列、第 2 列、第 1 列稳定排序。最后，它会被正确排序。说服自己。（顺便说一下，该算法称为基数排序）

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

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

于 2009-10-05T00:50:18.377 回答
81

一种稳定的排序算法是按照它们在输入中出现的相同顺序对相同的元素进行排序的算法，而不稳定的排序可能不满足这种情况。-我感谢我的算法讲师 Didem Gozupek 提供了对算法的见解。

由于某些人不了解演示文稿的逻辑的一些反馈，我再次需要编辑问题。它说明了对第一个元素进行排序。另一方面，您可以考虑由键值对组成的插图。

稳定的排序算法：

  • 插入排序
  • 合并排序
  • 冒泡排序
  • 蒂姆排序
  • 计数排序
  • 块排序
  • 四边形
  • 图书馆排序
  • 鸡尾酒调酒器
  • 侏儒排序
  • 奇偶排序

不稳定的排序算法：

  • 堆排序
  • 选择排序
  • 壳排序
  • 快速排序
  • Introsort（服从快速排序）
  • 树排序
  • 循环排序
  • 平滑排序
  • 比赛排序（以Hesapsort为准）

在此处输入图像描述

于 2017-05-06T14:14:42.660 回答
28

排序稳定性意味着具有相同键的记录在排序前后保持其相对顺序。

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

如果您不需要稳定性，您可以使用库中的快速、占用内存的算法，例如堆排序或快速排序，而不必理会它。

如果你需要稳定性，那就更复杂了。与不稳定算法相比，稳定算法具有更高的 big-O CPU 和/或内存使用率。因此，当您拥有大型数据集时，您必须在 CPU 或内存之间做出选择。如果您在 CPU 和内存方面都受到限制，那么您就有问题了。一个好的折衷稳定算法是二叉树排序；Wikipedia 文章有一个基于 STL 的非常简单的 C++ 实现。

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

于 2009-10-05T01:47:37.710 回答
21

这取决于你做什么。

想象一下，您有一些带有名字和姓氏字段的人员记录。首先，您按名字对列表进行排序。如果您随后使用稳定的算法按姓氏对列表进行排序，您将得到一个按名字和姓氏排序的列表。

于 2009-10-05T00:47:36.417 回答
16

稳定性很重要有几个原因。一个是，如果不需要通过交换两条记录来交换它们，则可能会导致内存更新，页面被标记为脏，需要重新写入磁盘（或另一个慢速介质）。

于 2009-10-05T00:47:10.807 回答
4

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

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

参考资料： http: //www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

于 2016-11-07T07:25:55.000 回答
3

我知道对此有很多答案，但对我来说，罗伯特哈维的这个答案更清楚地总结了它：

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

来源

于 2018-03-16T05:52:00.027 回答
1

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

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

例如，您有一个数据列表，其中包含所有玩家在游戏中使用等级 [L] 清理迷宫的时间成本 [T]。假设我们需要根据玩家清理迷宫的速度对他们进行排名。但是，还有一条附加规则：无论花费多长时间，清理迷宫的玩家等级越高，等级越高。

当然，您可以尝试使用一些遵循规则的算法将配对值 [T,L] 映射到实数 [R]，然后使用 [R] 值对所有玩家进行排名。

但是，如果稳定排序是可行的，那么您可以简单地按 [T]（速度更快的玩家优先）然后按 [L] 对整个列表进行排序。在这种情况下，玩家的相对顺序（按时间成本）在您按他们清理的迷宫级别分组后不会改变。

PS：当然，两次排序的方法并不是解决特定问题的最佳方法，但要解释海报的问题就足够了。

于 2016-07-30T09:23:39.350 回答
0

稳定排序将始终在相同的输入上返回相同的解决方案（排列）。

例如 [2,1,2] 将使用稳定排序作为排列 [2,1,3] 进行排序（首先是索引 2，然后是索引 1，然后是排序输出中的索引 3）这意味着输出总是以相同的方式打乱。其他不稳定但仍然正确的排列是[2,3,1]。

快速排序不是稳定的排序，相同元素之间的排列差异取决于选择枢轴的算法。一些实现是随机选择的，并且可以使用相同的算法进行快速排序，从而在相同的输入上产生不同的排列。

稳定的排序算法是必要的确定性的。

于 2009-10-05T00:49:52.560 回答
0

更多需要稳定排序的例子。数据库是一个常见的例子。以交易数据库为例，包括姓氏、购买日期、购买时间、商品编号、价格。假设数据库通常按日期|时间排序。然后进行查询以按姓氏|名字制作数据库的排序副本，因为稳定的排序保留了原始顺序，即使查询比较只涉及姓氏，每个姓氏的事务也会|名字按数据|时间顺序。

一个类似的例子是经典的 Excel，它一次将排序限制为 3 列。要对 6 列进行排序，首先对最不重要的 3 列进行排序，然后对最重要的 3 列进行排序。

稳定基数排序的一个经典示例是卡片排序器，用于按以 10 为基数的数字列的字段进行排序。卡片从最低有效位到最高有效位排序。每次通过时，都会读取一副纸牌，并根据该列中的数字将其分成 10 个不同的箱子。然后将 10 张纸牌按顺序放回输入槽（“0”牌在前，“9”牌在后）。然后下一列完成另一遍，直到对所有列进行排序。实际卡片分拣机有超过 10 个垃圾箱，因为一张卡片上有 12 个区域，一列可以是空白的，并且有一个误读垃圾箱。要对字母进行排序，每列需要 2 遍，第 1 遍用于数字，第 2 遍用于 12 11 区域。

后来（1937 年）出现了卡片整理（合并）机器，可以通过比较字段来合并两副卡片。输入是两副已经分类的牌，一个主牌和一个更新牌。整理者将这两个卡片组合并为一个新的主库和一个存档库，该库可选地用于主副本，以便新主库只有在出现重复时才会有更新卡。这可能是原始（自下而上）合并排序背后的想法的基础。

于 2020-05-23T13:39:49.923 回答