排序算法稳定有什么好处？

Question

如果它保持具有相等键的元素的相对顺序,则称其为稳定的.我想我的问题是,维持这种相对秩序有什么好处？有人能举个例子吗？谢谢.

Answer 1

它使您的排序能够在多种条件下"链接".

假设您有一个以随机顺序排列名字和姓氏的表格.如果按名字排序,然后按姓氏排序,则稳定排序算法将确保具有相同姓氏的人员按名字排序.

例如:

• 史密斯,阿尔弗雷德
• 史密斯,泽德

将保证以正确的顺序.

Answer 2

如果排序算法保留重复键的顺序,则它是稳定的.

好的,很好,但为什么这很重要？那么,当我们希望根据不同的密钥对同一数据进行多次排序时,就会出现排序算法中的"稳定性"问题.

有时数据项有多个键.例如,可能是(唯一的)主键,例如社会保险号,或学生识别号,以及一个或多个辅助键,例如居住城市或实验室部分.我们可能希望根据多个密钥对这些数据进行排序.问题是,如果我们根据一个键对相同的数据进行排序,然后根据第二个键,第二个键可能会破坏第一个排序所实现的排序.但如果我们的第二种类型是稳定的,那么这种情况就不会发生.

从稳定的排序算法

Answer 3

优先级队列就是一个例子.说你有这个:

1. (1,"鲍勃")
2. (3,"账单")
3. (1,"简")

如果您从最小到最大的数字排序,不稳定的排序可能会这样做.

1. (1,"简")
2. (1,"鲍勃")
3. (3,"账单")

......但随后"jane"领先于"bob",尽管它应该是另一种方式.

通常,它们可用于在多个步骤中对多个条目进行排序.

Answer 4

并非所有排序都基于整个值.考虑一个人的名单.我可能只想用他们的名字来排序,而不是他们所有的信息.使用稳定的排序算法,我知道如果我有两个名为"John Smith"的人,那么他们的相对顺序将被保留.

Last     First       Phone
-----------------------------
Wilson   Peter       555-1212
Smith    John        123-4567
Smith    John        012-3456
Adams    Gabriel     533-5574

由于两个"约翰史密斯"已经"排序"(他们按照我想要的顺序),我不希望他们改变立场.如果我按顺序对这些项目进行排序,那么首先使用不稳定的排序算法,我最终可能会这样:

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

(你看到两个"约翰史密斯"已经换了位置).这不是我想要的.

如果我使用稳定的排序算法,我将保证获得第一个选项,这就是我所追求的.

Answer 5

一个例子:

假设您有一个包含电话号码对的数据结构和调用它们的员工.每次通话后都会添加一个号码/员工记录.某些电话号码可能由几个不同的员工呼叫.

此外,假设您要按电话号码对列表进行排序,并为前两个拨打任何给定号码的人提供奖励.

如果您使用不稳定的算法排序,则可能无法保留给定数字的呼叫者的顺序,并且错误的员工可以获得奖励.

稳定的算法可确保每个电话号码的正确2名员工获得奖金.

Answer 6

这意味着如果您想按专辑排序,按轨道号排序,您可以先单击曲目编号,然后排序 - 然后单击专辑名称,并且每个专辑的曲目编号保持正确的顺序.

Answer 7

一种情况是您想要按多个键排序.例如,要对名字/姓氏对列表进行排序,您可以先按名字排序,然后按姓氏排序.

如果你的排序不稳定,那么你将失去第一种类型的好处.