各种排序算法的"稳定"和"不稳定"是什么意思？

Question

有人可以解释与各种排序算法相关的"稳定"和"不稳定"含义>如何确定算法是否稳定,以及不稳定排序算法通常具有哪些应用程序(因为它们不稳定)？

Answer 1

如果排序算法被称为"不稳定",这意味着对于排名相同的任何项目,绑定成员的顺序不保证与该集合的连续排序保持相同.对于"稳定"排序,绑定的条目在排序时总是以相同的顺序结束.

对于应用程序的示例,快速排序算法不稳定.这对于按优先级排序操作(如果两个操作具有相同的优先级,您不太可能关心首先执行绑定的哪些元素)这样的工作正常.

另一方面,稳定的排序算法对于诸如在线游戏的排行榜之类的东西是有益的.如果您使用不稳定排序,按点排序(例如),那么在网页上查看排序结果的用户可能会在页面刷新时遇到不同的结果,并且诸如分页结果之类的操作将无法正常运行.

Answer 2

稳定的排序保留相同项目的顺序.通过将行索引附加到键,可以使任何排序稳定.不稳定的排序,例如堆排序和快速排序,例如本身没有这个属性,但是它们被使用是因为它们比稳定排序更快更容易编码.据我所知,没有其他理由可以使用不稳定的排序.