排序算法穩定或不穩定的原因是什麼？

我想了解排序算法變得穩定或不穩定的主要原因。我明白，如果我們爲元素添加一個更多的位置關鍵字，每個不穩定的算法都會變得穩定。（但它可以影響速度和內存使用）。我也明白，在不穩定的排序元素總是改變的地方。排序算法穩定或不穩定的原因是什麼？

但是它的主要原因是什麼？是否因爲在某些情況下我們使用分治策略？

爲什麼給定的排序算法不穩定很容易找出，其原因不是通用的 - 每個工作原理都不同，因此大多數原因不同。 – Dukeling

@Dukeling所以我應該問一個關於具體案例的問題？ –

是的，你可能應該。在任何情況下，唯一可能的通用答案是「穩定的排序算法是穩定的，因爲它不會改變比較相等的元素的順序」，這只是重申定義。 –

它取決於算法使用的比較和交換。通常，如果數組中的遙遠對象之間發生比較和交換，而沒有先查看其中的元素，則排序將不穩定。

2013-11-22 17:38:23

我可能會添加諸如「沒有查看第一個之間的元素」之類的東西。就在我頭頂，插入排序和選擇排序可以從數組的一側進行比較和交換，但仍然穩定（可以使選擇排序穩定）。 – Dukeling

@Dukeling，感謝您的建議，我逐字添加。 –

沒有理由。穩定性僅僅是一個屬性，就是存在。有時候，算法是絕對有機會穩定的（創建者心中沒有穩定性）。大多數時候算法是穩定的，因爲創建者需要這樣做。

2013-11-22 17:33:55 Dialecticus

回答