问堆排序不被视为稳定排序算法的原因

EN

稳定排序:不改变相同/相等元素的相对位置的排序。 例如, I/P: 2、4、3(a)、5、1、3(b) O/P: 1、2、3(a)、3(b)、4、5 在I/P中，3(b)在3(a)之后，相同的在O/P中保持不变。

这是很容易解释的。让我们以以下例子为例：

3,3,2,1

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

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

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

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

然后将大小减小1，堆化操作为applied.Therefore，新的大小为3，前三个元素已经满足堆的属性。

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

同样，我们将从堆中提取最大值，这是第一个元素，并将其放在最后一个位置。

但由于现在的大小是3，最后一个位置是3(a)，因此我们得到：

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

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

最终结果是

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

因为它不能保证当它在被排序的集合中遇到两个相等的元素时，它们的位置将被保留。让我们假设这个集合：3 2 2 1。当该算法遇到2，并与2进行比较时，它可能会逆转它们。排序算法稳定性。顺便说一句，如果您不关心收藏中相同项目的顺序，那么您可以选择最快的一个。

你应该读这。

堆排序使用二进制堆，所使用的数据结构和算法使堆排序不稳定。