为什么堆排序不稳定？

Question

为什么堆排序不稳定？

42

我在尝试理解为什么堆排序不稳定。

我已经搜索过了，但没有找到一个好的、直观的解释。

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

感谢你的帮助！

- JMS

6个回答

30

堆排序最终的结果序列是从创建的堆中按照纯大小顺序（基于关键字段）删除项目得来的。

关于原始序列中项目的顺序的任何信息都在先进行的堆创建阶段中丢失了。

- Baldrick

21

稳定排序指如果两个元素具有相同的键，它们保持原来的顺序或位置不变。但是堆排序并非如此。

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

从这里得知：

在排序（升序）时，堆排序首先选择最大的元素并将其放置在列表的最后一个位置。因此，第一个被选择的元素留在最后，第二个被选择的元素留在排序列表的倒数第二个位置。

再次，Build-Max-Heap过程是这样工作的：在构建堆树时，它会保持相同值（例如：3a，3b）的顺序。对于提取最大元素，它也是从根开始工作，并尽量保持树的结构（除了Heapify的更改）。

因此，对于具有相同值（[3a，3b]）的元素，堆排序会先选择3a，然后将其放置在3b的右侧。因此，在按升序排列的列表中，我们会在列表中先看到3b，然后才是3a。

如果您使用（3a，3b，3b）进行堆排序，则可以可视化此情况。

- Rahul Tripathi

11

我知道这个回答有点晚，但我想在此添加我的建议。考虑一个包含3个整数的简单数组，2,2,2。现在，如果使用构建最大堆函数来构建最大堆，您会发现存储输入的数组没有改变，因为它已经是最大堆形式。现在，在堆排序的第一次迭代中将树的根放置在数组的末尾时，数组的稳定性已经丧失了。所以这里有一个堆排序不稳定的简单示例。

- Dipendra bhatt

2

我认为这应该高得多。 - Essam

9

稳定排序算法可以使输入中重复元素的顺序在输出中保持不变。

堆排序包含两个步骤：

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

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的）在堆排序数组中的顺序与它们在输入中出现的顺序不同，因此堆排序不是稳定的！

- user0904

1

假设有一个大小为n（任意值）的数组，并且如果堆中有两个连续的元素（假设为15），并且它们的父索引具有像4和20这样的值。（这是实际顺序（....4,20 ,.....,15,15.....）。4和第一个15的相对顺序保持不变，但由于20>15，第二个15会根据堆排序算法移动到前面（交换），相对顺序消失。

- Karthik Priyatham

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- KD157 · Accepted Answer

堆排序不稳定的示例

考虑数组21 20a 20b 12 11 8 7（已经按照大根堆的格式排好序）

这里的20a = 20b 只是为了区别我们表示它们的顺序，所以我们用20a和20b来表示

堆排序首先删除并将21放置在最后一个索引位置，然后将20a移除并放置在倒数第二个索引位置，将20b放到倒数第三个索引位置，因此经过堆排序后，该数组如下:

7 8 11 12 20b 20a 21.

它不保留元素的顺序，因此无法稳定。