sorting - 为什么堆排序不稳定？

Question

我试图理解为什么堆排序不稳定。我用谷歌搜索了这个，但没有找到一个好的、直观的解释。

我理解稳定排序的重要性——它允许我们基于多个键进行排序，这可能非常有益（即，进行多次排序，每个排序基于不同的键。由于每种排序都会保留元素的相对顺序，以前的排序可以加起来给出一个按多个标准排序的元素的最终列表）。但是，为什么 heapsort 也不保留这个呢？

谢谢你的帮助！

Answer 1

堆排序不稳定的例子

考虑数组21 20a 20b 12 11 8 7（已经是最大堆格式）

这里20a = 20b只是为了区分我们将它们表示为的顺序20a和20b

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

7 8 11 12 20b 20a 21.

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

Answer 2

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

任何关于原始序列中项目排序的信息都在堆创建阶段丢失，这是最先出现的。

Answer 3

稳定意味着如果两个元素具有相同的键，它们将保持相同的顺序或位置。但堆排序并非如此。

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

从这里：

排序（按升序）时，堆排序首先使最大元素达到峰值，并将其放在列表的最后一个。因此，第一个被选中的元素保持在最后，第二个被选中的元素保持在排序列表中的倒数第二个元素。

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

那么，对于具有相同值 [3a,3b] 的元素，堆排序会在 3b 之前选择 3a，但将 3a 放在 3b 的右侧。因此，由于列表按升序排序，我们在列表中得到 3b 之前的 3a 。

如果您尝试使用 (3a,3b,3b) 进行堆排序，那么您可以想象这种情况。

Answer 4

稳定的排序算法对元素进行排序，使得输入中重复元素的顺序也保持在输出中。

堆排序涉及两个步骤：

• 堆创建
• 从堆树中删除根元素并将其添加到一个新数组中，该数组将按顺序排序

1. 堆创建期间的订单中断

假设输入数组是 {1, 5, 2, 3, 2, 6, 2}，为了查看 2 的顺序，假设它们是 2a、2b 和 2c，因此数组将是 {1, 5, 2a、3、2b、6、2c}

现在，如果您从中创建一个堆（此处为最小堆），它的数组表示将是 {1, 2b, 2a, 3, 5, 6, 2c} ，其中 2a 和 2b 的顺序已经改变。

2. 删除根元素期间的顺序中断

现在，当我们必须从堆中删除根元素（在我们的例子中为 1）以将其放入另一个新数组时，我们将其与最后一个位置交换并从那里删除，因此将堆更改为 {2c, 2b, 2a, 3、5、6}。我们重复相同的操作，这次我们将从堆中删除“2c”并将其放在我们放置“1”的数组末尾。

当我们完成重复此步骤直到堆为空并且每个元素都转移到新数组时，新数组（已排序）看起来像 {1, 2c, 2b, 2a, 3, 5, 6}。

堆排序的输入： {1, 5, 2a, 3, 2b, 6, 2c} -->输出： {1, 2c, 2b, 2a, 3, 5, 6}

因此我们看到重复元素（2）在堆排序数组中的顺序与它们出现在输入中的顺序不同，因此堆排序不稳定！

Answer 5

我知道这是一个迟到的答案，但我会在这里加上我的 2 美分。考虑一个由 3 个整数组成的简单数组。2,2,2 现在如果你使用 build max heap 函数来构建一个 max heap，你会发现存储输入的数组并没有改变，因为它已经是 Max heap 形式了。现在，当我们在堆排序的第一次迭代中将树的根放在数组的末尾时，数组的稳定性已经消失了。所以你有一个堆排序不稳定性的简单例子。

Answer 6

假设取一个大小为 n （任意值）的数组，如果堆中有两个连续的元素（假设 15），并且它们的父索引的值类似于 4 和 20。（这是实际顺序（....4,20 ,.....,15,15.....). 4 和第 1 个 15 的相对顺序保持不变，但是当 20>15 时，第 2 个 15 出现在堆排序算法中定义的前面（交换），相对顺序消失了。