MergeSort執行穩定性

Question

mergesort的實現會影響其穩定性嗎？

例如，如果我們使用數組來實現合併排序，是否比鏈接列表實現的合併排序不穩定？

Answer 1

對於數組或鏈表的合併排序，自頂向下（遞歸）和自底向上（迭代）實現的大多數實現都是穩定的。關鍵因素是在合併函數中，只要合併函數在「右」元素之前移動相等的「左」元素，它將是穩定的。比較可以是「左」元素< =「右」元素，或者在C++標準庫的情況下，只使用小於比較的元素，其比較爲「右」元素<「左」元素，所以「左」元素如果它是< =「right」元素將被移動。

另一個可能的問題是對於小組元素使用非穩定排序方法的混合合併排序。

通常，交換相鄰元素的排序（如冒泡排序）通常是穩定的，而交換非相鄰元素的排序（如快速排序）通常不穩定。

Answer 2

合併排序應該對它們都是穩定的。無論你使用列表還是數組，都取決於你使用的是什麼。

Answer 3

如果排序方法保持數組中相等鍵的元素的相對順序，則它是穩定的。

自上而下和自下而上都是穩定的方法。它獨立於數組或鏈接列表。