什么是排序算法的稳定性,为什么它很重要？
Dar*_*der 236 language-agnostic sorting algorithm stability
我很好奇,为什么稳定性在排序算法中是否重要？
Joe*_*ams 306
如果具有相等键的两个对象在排序输出中以与要排序的输入数组中出现的顺序相同的顺序出现,则称排序算法是稳定的.一些排序算法本质上是稳定的,如插入排序,合并排序,冒泡排序等.并且一些排序算法不是,如堆排序,快速排序等.
背景:"稳定"排序算法按顺序保存具有相同排序键的项目.假设我们有一个5个字母的单词列表:
peach
straw
apple
spork
如果我们只按每个单词的第一个字母对列表进行排序,那么稳定排序会产生:
apple
peach
straw
spork
在一个不稳定的排序算法,straw或者spork可以互换,但在稳定的一个,它们留在相同的相对位置(即,由于straw前出现spork在输入,它也出现之前spork在输出).
我们可以使用这个算法对单词列表进行排序:第5列,然后是4,然后是3,然后是2,然后是1的稳定排序.最后,它将被正确排序.说服自己.(顺便说一句,该算法称为基数排序)
现在回答你的问题,假设我们有一个名字和姓氏的列表.我们被要求"按姓氏排序,然后先排序".我们可以先按名字排序(稳定或不稳定),然后按姓氏进行稳定排序.在这些排序之后,列表主要按姓氏排序.但是,如果姓氏相同,则对名字进行排序.
您不能以相同的方式堆叠不稳定的排序.
- **示例 - **假设您有一个列表,其中每个项目都包含有关航班目的地和出发时间的信息.您首先根据时间对列表进行排序.然后我们根据目的地对其进行排序.如果第二种类型是__stable__,我们现在将所有航班一起绑定到同一目的地并按出发时间的递增顺序排列.如果它不稳定,它们将不会按时间顺序增加. (11认同)
- 我不明白行_ ..相同的排序键_？你在这里关键是什么意思？请解释声明_ ..相同的排序键_ (3认同)
- @ user1416486:我们只按第一个字母排序.根据这个假设,"稻草"和"spork"比较相等.稳定的排序将保持输入的顺序,而不稳定的排序不能保证."正确"取决于应用程序.大多数编程语言中的排序功能允许用户提供自定义排序功能.如果用户的函数将不同的项视为相等(例如,相同的名字,不同的姓氏),则有助于知道是否将保留原始订单.有关实际示例,请参阅[OCaml的数组排序函数](http://is.gd/7gDhtD). (2认同)
- @saplingPro：“排序键”是指您对项目进行排序的东西。因此，当按首字母排序时，对于每个项目，其“排序关键字”即为其首字母。 (2认同)
snr*_*snr 42
一个稳定的排序算法是按照输入中出现的相同顺序对相同元素进行排序,而不稳定排序可能不满足这种情况.
稳定的排序算法:
- 插入排序
- 合并排序
- 冒泡排序
- 蒂姆排序
- 计数排序
不稳定的排序算法:
- 堆排序
- 选择排序
- 壳排序
- 快速排序
- @erhun 我相信他只按第一个数字（逗号前的那个）排序，并使用第二个数字作为参考，让您看到第一个 9 与第二个 9 不同。 (7认同)
- 你的价值观不平等.你比较9,7和9,8,但根据稳定性检查你需要相同的值,如9,7或两者9,8.并且在稳定算法中应该以相同的值排序相同的值. (2认同)
Bob*_*phy 18
排序稳定性意味着具有相同键的记录在排序之前和之后保持其相对顺序.
因此,只有当您正在解决的问题需要保留相对顺序时,稳定才有意义.
如果你不需要稳定性,你可以使用库中的快速,内存啜饮算法,比如heapsort或quicksort,并忘记它.
如果你需要稳定性,那就更复杂了.稳定算法比不稳定算法具有更高的大O CPU和/或内存使用率.因此,当您拥有大型数据集时,您必须在击败CPU或内存之间进行选择.如果你受到CPU和内存的限制,那就有问题了.一个好的折衷稳定算法是二叉树排序; 在维基百科的文章具有基于STL一个可怜容易C++实现.
您可以通过将原始记录号添加为每个记录的最后一个键来将不稳定算法变为稳定算法.
- @augenss如果两条记录都有键“foo”，那么在进行排序之前，将它们更改为“foo_00001”和“foo_00002”之类的内容。当您进行排序时，这将保留两个键的原始顺序。然后，当您完成排序后，将两个键更改回“foo”。 (2认同)
sve*_*ens 14
这取决于你做了什么.
想象一下,你有一些带有名字和姓氏字段的人物记录.首先,按名字对列表进行排序.如果您使用按姓氏的稳定算法对列表进行排序,则您将拥有按名字和姓氏排序的列表.
- 我认为你的意思是"最后一个名字".姓氏通常是姓氏. (4认同)