如果一个排序算法被称为“不稳定”,这意味着对于任何排名相同的项目,相同排名成员的顺序不能保证在对该集合进行连续排序时保持不变。对于“稳定”的排序,相同排名的条目将始终以相同的顺序排列。举个应用的例子,快速排序算法是不稳定的。这对于像按优先级排序操作这样的事情是很好的(如果两个操作的优先级相同,则您可能不会关心哪些细节先执行)。另一方面,稳定的排序算法适用于在线游戏排行榜之类的东西。如果您使用不稳定的排序(例如按积分排序),那么查看网页上排序结果的用户可能会在页面刷新和操作(如浏览结果)中体验到不同的结果,而这些操作将无法正确地运行。
稳定排序保留相同项目的顺序。通过将行索引附加到键上,可以使任何排序都变得稳定。不稳定的排序(例如堆排序和快速排序)本质上没有这个属性,但它们之所以被使用是因为它们往往比稳定排序更快且更易于编码。据我所知,没有其他理由使用不稳定的排序。