MergeSort实现稳定性

Question

并购的实施是否会影响其稳定性？

例如，如果我们使用数组实现合并排序，这比合并排序的链接列表实现更不稳定吗？

Answer 1

对于数组或链接列表的合并排序和自底向上(迭代)实现的大多数实现是稳定的。关键因素是合并函数，只要合并函数在“右”元素之前移动相等的“左”元素，它就会稳定。比较可以是“左”元素“<=”“右”元素，也可以是C++标准库(只使用比“比较”更少)，其比较是“右”元素<“左”元素，因此如果“左”元素是<=“右”元素，则“左”元素将被移动。

另一个可能的问题是混合合并排序，它使用了一种不稳定的元素组排序方法。

通常，交换相邻元素的排序(如气泡排序)通常是稳定的，而交换非相邻元素的排序(如快速排序)通常不稳定。

Answer 2

合并排序应该对它们都是稳定的。您是否使用列表或数组更多地取决于您使用它的目的。

Answer 3

如果排序方法保持数组中具有相等键的元素的相对顺序，则排序方法是稳定的。

自顶向下和自下而上的实现都是稳定的方法。它独立于数组或链表。