如果排序算法能够保持具有相等键值的元素之间的相对顺序，则称该排序为稳定排序。我的问题实际上是，维护这种相对顺序的好处是什么？可以给出一个例子吗？谢谢。
10个回答
65
它使您的排序可以通过多个条件“链接”起来。
假设您有一个包含随机顺序的名字和姓氏的表格。如果您按照名字排序，然后按照姓氏排序，稳定的排序算法将确保具有相同姓氏的人按照名字排序。
例如：
- Smith, Alfred
- Smith, Zed
将被保证处于正确的顺序。
- Matt Brunell
3
4为什么不在比较条件中包含这个名字的首尾？那样你只需要排序一次。 - SebastianK
25在你不知道条件的情况下，它非常有用。想象一下一个ListView，在这个ListView中，用户可以点击某一列进行排序，然后再点击另一列进行进一步的排序。 - Matt Brunell
这个答案应该被接受。我刚刚花了半小时去看其他的回答，他们解释了技术定义（这些定义很容易在Google上找到），但没有清晰地表达使用稳定性的底线。 - Tyler Gannon
43
一个排序算法是稳定的，如果它保留了重复键的顺序。
好的，不过这为什么很重要呢？嗯，当我们希望根据不同的关键字多次对相同的数据进行排序时，排序算法中“稳定性”的问题就会出现。
有时数据项具有多个关键字。例如，可能有一个（唯一的）主键，如社会保险号码或学生识别号码，以及一个或多个辅助键，如居住城市或实验室部分。我们可能非常想根据一个以上的关键字对这些数据进行排序。问题是，如果我们根据一个关键字对相同的数据进行排序，然后再根据第二个关键字进行排序，第二个关键字可能会破坏第一个排序所达到的顺序。但如果我们的第二个排序是稳定的，这种情况就不会发生。
来自稳定排序算法
好的，不过这为什么很重要呢？嗯，当我们希望根据不同的关键字多次对相同的数据进行排序时，排序算法中“稳定性”的问题就会出现。
有时数据项具有多个关键字。例如，可能有一个（唯一的）主键，如社会保险号码或学生识别号码，以及一个或多个辅助键，如居住城市或实验室部分。我们可能非常想根据一个以上的关键字对这些数据进行排序。问题是，如果我们根据一个关键字对相同的数据进行排序，然后再根据第二个关键字进行排序，第二个关键字可能会破坏第一个排序所达到的顺序。但如果我们的第二个排序是稳定的，这种情况就不会发生。
来自稳定排序算法
- dirkgently
3
2我没有给你点踩，但是你所做的只是从一个网站上复制数据。其他人实际上费了功夫来解释问题，也许这就是原因。对我来说似乎不值得一点，但其他人可能会这么认为。 - Adam Robinson
1在我看来，这并不是重复造轮子，同时也要适当引用并注明出处。但你的情况可能有所不同。 - dirkgently
5点赞；简洁的引文和一个可信来源的链接比一堆漂浮在这个地方的答案更好。 - Kevin
17
优先队列是其中一个例子。假设你有以下数据：
- (1，"bob")
- (3，"bill")
- (1，"jane")
如果你按照数字从小到大排序，一个不稳定的排序可能会做出这样的结果:
- (1，"jane")
- (1，"bob")
- (3，"bill")
...但是"jane"超过了"bob"，虽然应该是相反的顺序。
通常，它们用于在多个步骤中排序多个条目。
- Unknown
1
有了正确的比较逻辑，这种情况就不会发生了。（即：也要比较字符串） - M.kazem Akhgary
14
并不是所有的排序都基于整个值。考虑一个人员列表，我可能只想按照他们的姓名进行排序，而不是他们的全部信息。使用稳定的排序算法，我知道如果有两个名叫“John Smith”的人，则他们的相对顺序将得到保留。
Last First Phone
-----------------------------
Wilson Peter 555-1212
Smith John 123-4567
Smith John 012-3456
Adams Gabriel 533-5574
由于这两个“John Smith”已经是“排序好的”（他们按我想要的顺序），因此我不希望它们改变位置。如果我使用一个不稳定的排序算法按姓和名排序这些项目，我可能会得到以下结果：
Last First Phone
-----------------------------
Adams Gabriel 533-5574
Smith John 123-4567
Smith John 012-3456
Wilson Peter 555-1212
这正是我想要的，否则我可能会得到这个：
Last First Phone
-----------------------------
Adams Gabriel 533-5574
Smith John 012-3456
Smith John 123-4567
Wilson Peter 555-1212
你可以看到这两个 "John Smith" 已经交换了位置。这不是我想要的。
如果我使用一个稳定的排序算法，我将保证得到第一个选项，这正是我想要的。
- Adam Robinson
1
点赞；没有其他人提到，保留“相对”顺序。 - Prateek Jain
10
一个例子：
假设你有一个数据结构，其中包含电话号码和拨打这些电话的雇员的配对信息。每次通话后都会添加一个号码/雇员记录。某些电话号码可能会被多个不同的员工拨打。
此外，假设你想按电话号码对列表排序，并向每个给定号码的前两位拨打电话的人提供奖金。
如果你使用不稳定的算法进行排序，可能无法保护给定电话拨打者的顺序，错误的员工可能会得到奖金。
稳定的算法可以确保每个电话号码的正确2名员工获得奖金。
- JeffH
8
这意味着如果你想按专辑排序，而且还要按曲目编号排序，那么你可以先点击曲目编号进行排序，然后再点击专辑名称，这样每个专辑的曲目编号仍然保持正确的顺序。
- Joe Koberg
1
我想知道有多少人意识到它是这样工作的？看起来几乎像逆波兰表示法。 - Mark Ransom
5
有一种情况是当你想按多个键排序时。例如，要对名字/姓氏对列表进行排序，您可能首先按名字排序，然后按姓氏排序。
如果您的排序不稳定，那么您将失去第一个排序的好处。
- John Carter
4
稳定排序对于多个关键字的优势是可疑的，您总是可以使用一种比较方式同时比较所有关键字。只有在一次排序一个字段时才具有优势，例如单击列标题 - Joe Koberg 提供了一个很好的例子。
如果您能够负担得起向记录添加序列号并在出现等效键时使用它作为平局决胜者，则可以将任何排序转换为稳定排序。
最大的优势是当原始顺序本身具有某种意义时。我想不出一个好的例子，但当我在思考时，我看到 JeffH 给出了一个例子。
如果您能够负担得起向记录添加序列号并在出现等效键时使用它作为平局决胜者，则可以将任何排序转换为稳定排序。
最大的优势是当原始顺序本身具有某种意义时。我想不出一个好的例子，但当我在思考时，我看到 JeffH 给出了一个例子。
- Mark Ransom
0
假设您正在对具有两个字段的输入集进行排序，而您只对第一个字段进行排序。 '|'字符分隔字段。
在输入集中，您有许多条目，但是您有3个条目看起来像
。 。 。 AAA | 拖车 。 。 。 AAA | 租车 。 。 。 AAA | 管道工程 。 。 。
现在，当您完成排序时，您希望所有包含AAA的字段都在一起。
稳定的排序将为您提供： 。 。 。 AAA | 拖车 AAA | 租车 AAA | 管道工程 。 。 。
即，具有相同排序键AAA的三个记录在输出中与它们在输入中的顺序相同。请注意，它们没有按第二个字段排序，因为您没有对记录的第二个字段进行排序。
不稳定的排序将为您提供： 。 。 。 AAA | 管道工程 AAA | 租车 AAA | 拖车 。 。 。
请注意，记录仍然仅按第一个字段排序，并且第二个字段的顺序与输入顺序不同。
不稳定排序有可能更快。稳定排序往往模仿非计算机科学家/非数学专业人士在排序时脑海中的想法。例如，如果您使用索引卡进行插入排序，您很可能会得到一个稳定排序。
- Bruce ONeel
0
你不能总是一次性比较所有字段。举个例子：（1）内存限制，当你对一个大磁盘文件进行排序时，主内存中可能没有足够的空间来存储所有记录的所有字段；（2）对一个基类指针列表进行排序，其中某些对象可能是派生子类（你只能访问基类字段）。
此外，稳定的排序在给定相同输入时具有确定性输出，这对于调试和测试非常重要。
- dewtell
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接