爲什麼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在堆排序算法中定義（交換），相對順序不見了。