为什么heapsort不稳定？

Question

我想知道为什么heapsort不稳定。 我已经使用了这个，但没有找到一个好的，直观的解释。

我明白稳定排序的重要性 - 它允许我们根据多个关键字进行排序，这可能非常有益（例如，进行多次排序，每次排序都基于不同的关键字，因为每种排序都会保留相对关系元素的顺序，先前的排序可以加起来给出按多个标准排序的元素的最终列表）。 但是，为什么不会保存这个呢？

感谢您的帮助！

Answer 1

heapsort结果的最终序列来自以纯大小顺序（基于关键字段）从创建的堆中移除项目。

有关原始序列中项目排序的任何信息在堆创建阶段丢失，这是第一次。

Answer 2

稳定表示如果两个元素具有相同的键，则它们保持相同的顺序或位置。但是，对于堆排序，情况并非如此。

Heapsort不稳定，因为堆上的操作可以改变相等项目的相对顺序。

从here：

当排序（升序）堆排序第一峰最大 元素，并把它放在最后的名单。因此，具有 的元素首先被选中，保持最后，并且被挑选的元素 秒保持到排序列表中的倒数第二个元素。

同样，构建最大堆过程的工作原理是在构建堆树时保留相同值（例如：3a，3b）的顺序 。为了提取 它也从根开始工作的最大元素，并尝试保留树的结构（除了Heapify的变化）。

因此，对于具有相同值[3a，3b]的元素，在3b之前选择 3a但将3a置于3b的右边。所以，由于列表是 按升序排序，我们在列表3a前3a得到3b。

如果您尝试使用（3a，3b，3b）堆排序，则可以看到 的情况。

Answer 3

堆排序不稳定例如

考虑阵列21 20a 20b 12 11 8 7（已经在最大堆格式）

这里20a = 20b只是为了区分，我们代表他们为20a和20b

顺序虽然堆排序第一21是删除并放置在最后一个索引然后20a被删除，并放置在最后，但一个索引和20b在最后但两个索引，所以堆排序后，数组看起来像

7 8 11 12 20b 20a 21。

它不保留元素的顺序，因此不能稳定

Answer 4

假设取大小为n（任意值）的阵列，并且如果有两个连续元素在堆和如果（假定15）其父指标的值为4和20.（这是实际的订单（.... 4,20，.....，15,15 .....）。4和15的相对顺序保持不变但是当20> 15时，第2个15在堆排序算法中定义（交换），相对顺序不见了。