我试图理解为什么堆排序不稳定。我已经用谷歌搜索过这个，但没有找到一个好的、直观的解释。
我了解稳定排序的重要性 - 它允许我们基于多个键进行排序，这可能非常有益（即，进行多次排序，每个排序基于不同的键。由于每个排序都将保留元素的相对顺序，因此以前的排序可以加起来给出按多个条件排序的元素的最终列表）。但是，为什么堆排序不保留它呢？
感谢您的帮助！
堆排序不稳定示例
考虑数组21 20a 20b 12 11 8 7（已经采用最大堆格式）
这里20a = 20b只是为了区分我们将它们表示为20a和20b的顺序
当堆排序首先21被删除并放置在最后一个索引中时20a被删除并放置在最后一个索引中，20b放在最后一个索引中，但有两个索引，因此堆排序后数组看起来像
7 8 11 12 20b 20a 21 .
它不保留元素的顺序，因此不能稳定
堆排序结果的最终顺序来自以纯粹的大小顺序（基于键字段）从创建的堆中删除项目。
有关原始序列中项目排序的任何信息在堆创建阶段（首先出现）期间丢失。
稳定意味着如果两个元素具有相同的键，它们将保持相同的顺序或位置。但堆排序并非如此。
堆排序不稳定，因为堆上的操作可以更改相等项的相对顺序。
从这里：
排序时（按升序），堆排序首先达到最大值 元素并将其放在列表的最后一个。因此，具有 首先被选中，保持最后和已选择的元素 第二个保留到排序列表中的倒数第二个元素。
同样，构建最大堆过程的工作方式是保留顺序 在构建堆树时具有相同的值 （例如：3a，3b）。用于提取 最大元素它也从根开始工作并尝试保留 树的结构（堆的更改除外）。
那么，对于具有相同值 [3a，3b] 堆排序选择的元素会发生什么 3a 在 3b 之前，但将 3a 放在 3b 的右侧。所以，正如列表一样 按升序排序，我们在列表中 3A 之前得到 3b。
如果您尝试使用 （3a，3b，3b） 进行堆排序，那么您可以可视化 情况。
这是一个迟到的答案，但我会在这里添加我的 2 美分。考虑一个由 3 个整数组成的简单数组。2，2，2 现在，如果您使用构建最大堆函数构建最大堆，您会发现存储输入的数组没有更改，因为它已经是最大堆形式。现在，当我们在堆排序的第一次迭代中将树的根放在数组的末尾时，数组的稳定性已经消失了。所以这里有一个简单的堆排序不稳定的例子。
稳定的排序算法对元素进行排序，使得输入中重复元素的顺序也保持在输出中。
堆排序涉及两个步骤：
- 堆创建
- 从堆树中删除根元素并将其添加到将按顺序排序的新数组中
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）在堆排序数组中的顺序与它们在输入中出现的顺序不同，因此堆排序不稳定！
假设取一个大小为 n（任意值）的数组，并且堆中有两个连续的元素（假设为 15），并且它们的父索引的值为 4 和 20。这是实际订单（....4,20 ,.....,15,15.....).4 和 1st 15 的相对顺序保持不变，但随着 20>15，第 2 个 15 出现在堆排序算法中定义的 FRONT（swap），相对顺序消失了。