heapsort 為什麼是不穩定排序？

02-13

接觸到了穩定排序這個概念，然後仔細考慮了下接觸過的幾種演算法。
首先mergesort肯定是穩定排序，冒泡和插入也是。然後radix和counting sort也是。快排顯而易見不是。
可是堆排為什麼不是穩定排序啊？堆排的話不應該是判斷無序區是否滿足堆，然後把堆的節點和當前無序區的最後一個元素交換得來的么。如果每一次的比較都是固定的話，得到的結果應該也是固定的啊？為什麼會出現相同的數字的排序先後不同（同一list的多次排序）的情況。

========================================================================
感謝Amb Ba指出，之前概念有混淆！！！
現已弄明白heapsort確實不是穩定排序！！
嗯，想知道下穩定排序有什麼好處么？

你好像沒有理解排序穩定性的意思，穩定是指排序前後相同值的相對位置不變，而不是多次排序的結果中相同值的相對位置不變。

題主已經理解了穩定排序的定義，那我就說說穩定排序的好處。

好處就是如果對一個列表進行多次排序，比如說有姓名，性別，分數三個列。

我先按照分數進行排序，再按照性別進行排序，那麼我就知道男的最高分是誰，女的最高分是誰。

但是如果排序是不穩定的，就不能達到這種效果。

就比如說開飯的時候要排隊，大家呼呼啦啦地都去了，結果要求女生先打飯，而你是男生

穩定排序的結果是，老師把所有的女生全跑到前面了，而你面前的哪位男生剛才也是在你前面，沒有男生從你的後面跑到你的前面，也沒有男生從你的前面跑到你的後面，老師排了好多天都是這個規律。

不穩定排序的結果是：老師把所有的女生排到你的前面，但是某些原本在你後面的男生跑到你前面了，或者原本在你前面的男生跑到你後面了。

所以穩定排序就是為了防止第二種情況發生。也就是穩定排序是所用到的關鍵值相同的兩個在排序前後不發生順序變化。要是你不在乎這種變化，那就隨便了