java - 为什么堆排序不被认为是一种稳定的排序算法

Question

在 Java 中，堆排序似乎是最佳的排序算法，同时根据 http://www.sorting-algorithms.com/ 对随机数数组进行排序。 但我仍然读到堆排序不稳定，为什么会这样？在对数组或随机数进行排序时，哪种排序算法应该被认为是最佳算法？

Answer 1

Stable Sort: A sort which doesn't change the relative position of same/equal elements.

For example,
I/P: 2, 4, 3(a), 5, 1, 3(b)
O/P: 1, 2, 3(a), 3(b), 4, 5

In I/P 3(b) comes after 3(a) and the same stays intact in the O/P.

这很容易解释。让我们举个例子:

3,3,2,1

将前 3 个视为 3(a)，将第二个 3 视为 3(b)。

3(a),3(b),2,1

堆排序首先从最大堆中提取最大数，这是第一个元素，然后将其放在最后一个位置。

3(b),2,1,3(a)

然后 size 减 1 并应用 heapify 操作。因此新的 size 为 3，前三个元素已经满足堆属性。

现在是表明堆排序不稳定的步骤。

我们再次从堆中提取最大值，即第一个元素并将其放在最后一个位置。

但是因为大小现在是 3，所以最后一个位置是 3(a) 的左边，因此我们得到:

2,1,3(b),3(a)

正如我们所见，元素 3(a) 和 3(b) 的顺序与原始顺序相反，堆排序的剩余部分只会对前两个元素进行排序，因此，元素 3(a) 和 3(b) 将在其位置保持不变。这就是堆排序不稳定的原因。

最后的结果是

1,2,3(b),3(a)