有人能解释一下在各种排序算法中，“stable”和“unstable”是什么意思吗？如何确定算法是否稳定，不稳定的排序算法通常有哪些应用（因为它们是不稳定的）？
2个回答
64
如果一个排序算法被称为“不稳定”，这意味着对于任何排名相同的项目，相同排名成员的顺序不能保证在对该集合进行连续排序时保持不变。对于“稳定”的排序，相同排名的条目将始终以相同的顺序排列。
举个应用的例子，快速排序算法是不稳定的。这对于像按优先级排序操作这样的事情是很好的（如果两个操作的优先级相同，则您可能不会关心哪些细节先执行）。
另一方面，稳定的排序算法适用于在线游戏排行榜之类的东西。如果您使用不稳定的排序（例如按积分排序），那么查看网页上排序结果的用户可能会在页面刷新和操作（如浏览结果）中体验到不同的结果，而这些操作将无法正确地运行。
举个应用的例子，快速排序算法是不稳定的。这对于像按优先级排序操作这样的事情是很好的（如果两个操作的优先级相同，则您可能不会关心哪些细节先执行）。
另一方面，稳定的排序算法适用于在线游戏排行榜之类的东西。如果您使用不稳定的排序（例如按积分排序），那么查看网页上排序结果的用户可能会在页面刷新和操作（如浏览结果）中体验到不同的结果，而这些操作将无法正确地运行。
- user1898811
4
4编辑后的文本包括一些例子，说明为什么这种差异很重要。 - user1898811
3通常而言，不可用的排序方法会产生可预测的结果，也就是说，相同的数据输入时，它们不会给出不同的答案。因此，在其他值发生变化时，页面刷新只会显示相等项的不同顺序。这种不稳定性的原因在于使用树或类似的数据结构来组织数据。 - Peter Wooster
3值得注意的是，稳定排序更常见的用法是按多个键（key）进行排序。举个例子，如果你有一个表示人的对象数组，并且想要按年龄排序，当存在年龄相同的人时再按姓名（字典序）排序，那么可以先按姓名排序，然后再按年龄排序，使用稳定排序算法可以得到你想要的结果。 - Aaron Dufour
MIB 是稳定排序。（M-> 归并排序，I-> 插入排序，B-> 冒泡排序） - roottraveller
8
稳定排序保留相同项目的顺序。通过将行索引附加到键上，可以使任何排序都变得稳定。不稳定的排序（例如堆排序和快速排序）本质上没有这个属性，但它们之所以被使用是因为它们往往比稳定排序更快且更易于编码。据我所知，没有其他理由使用不稳定的排序。
- Peter Wooster
2
回到Azron在您的观点下面提出的观点和他提出的例子，这是否意味着我们在Windows中进行的网格排序是通过一种稳定排序实现的？ 网格排序意味着按日期和类型对文件夹中的文件进行排序。 - Bhupesh Pant
2在文件管理器和 Excel 等工具中进行的排序是稳定的，它们要么使用稳定排序，要么使用不稳定排序的稳定版本。 - Peter Wooster
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接