algorithm - 排序的稳定性 "factors"是什么？

Question

最近，我一直在学习各种排序方法，其中很多不稳定，即选择排序、快速排序、堆排序。我的问题是:导致排序不稳定的一般因素是什么？

Answer 1

大多数高效的排序算法都是高效的，因为它们将数据移动更长的距离，即每次移动都离最终位置更近。这种效率导致排序中的稳定性损失。例如，当您进行像冒泡排序这样的简单排序时，您会比较和交换相邻元素。在这种情况下，如果元素的顺序已经正确，则很容易不移动它们。但是说在快速排序的情况下，分区过程可能会选择移动，因此交换是最小的。例如，如果将下面的列表按数字 2 进行分区，最有效的方法是将第 1 个元素与第 4 个元素交换，将第 2 个元素与第 5 个元素交换

2 3 1 1 1 4
1 1 1 2 3 4

如果您注意到，现在我们已经更改了列表中 1 的顺序，导致它不稳定。

所以总而言之，一些算法非常适合稳定排序(如冒泡排序)，而另一些算法如快速排序可以通过仔细选择分区算法使其稳定，尽管以效率或复杂性为代价或两者。

我们通常根据算法最“自然”的实现来将算法分类为稳定或不稳定。