证明合并排序是稳定的

Question

我写了一个合并排序算法。当我运行以下测试时：

public static void main(String[] args){
    Integer[] arr = {3,7,9,11,0,-5,2,5,8,8,1};
    List<Integer> list = new ArrayList<>();
    list.addAll(Arrays.asList(arr)); // asList() returns fixed size list, so can't pass to mergesort()
    List<Integer> result = mergesort(list);
    System.out.println(result);
  }

我得到 [-5, 0, 1, 2, 3, 5, 7, 8, 8, 9, 11]，这是正确的。但是，我知道mergesort是一种稳定排序，那么如何编写一个测试来证明这两个8的顺序是原来的顺序呢？

编辑：由于我使用了 Integer class，而不是原始整数，我想我可以得到 hashCode() 因为 Integer 扩展了基础 Object class.

然而，当我尝试

Integer[] arr = {3,7,9,11,0,-5,2,5,8,8,1};
System.out.println(arr[8].hashCode());
System.out.println(arr[9].hashCode());

我只得到：

8
8

Answer 1

我能想到的最好方法是将数字包装在它们的包装器中 Integer class。如果您执行以下操作：

Integer eight = new Integer(8);
Integer anotherEight = new Integer(8);

a == b; //Returns false
a.equals(b); //Returns true

否则，如评论中所建议，您可以在 class 中添加一个额外字段以进行比较。

编辑：为了回答您的编辑，Integer.hashcode() 文档指出 hascode 是

equal to the primitive int value represented by this Integer object.

Answer 2

我认为使用简单的键值结构，比如 this or some of that

使用这个（简称）：

public class Tuple<X, Y> { 
  public final X x; 
  public final Y y; 
  public Tuple(X x, Y y) { 
    this.x = x; 
    this.y = y; 
  } 
}

你可以这样做：

  public static void main(String[] args)
  {
    Integer[] arr = {new Tuple(3,0),new Tuple(7,1),new Tuple(9,2) ,new Tuple(11,3), new Tuple(0,4), new Tuple(-5,5), new Tuple(2,6), new Tuple(5,7), new Tuple(8,8), new Tuple(8,9), new Tuple(1,10)};
    List<Tuple<Integer,Integer>> list = new ArrayList<>();
    list.addAll(Arrays.asList(arr)); // asList() returns fixed size list, so can't pass to mergesort()
    List<Integer> result = mergesort(list);
    System.out.println(result);
  }

而在合并排序的代码中，只合并第一项，让第二项相同，你应该先看到(8,8)，然后看到(8,9)

Answer 3

稳定性证明将涉及分析合并排序算法，而不是创建稳定性测试未失败的测试用例。首先分析自下而上的归并排序可能更简单。首先 n 个元素的数组被视为长度为 1 的 n 运行s 的数组，然后重复合并这些运行s 直到产生单个排序的运行。在 k 路合并排序中，如果来自 k 运行的当前元素相等，则将最左边的元素运行移动到输出数组，保持稳定性。

对于通常为 2 向的自上而下归并排序，适用相同的规则，当遇到相等元素时，移动左侧运行的元素，保持稳定性。

证明合并排序是稳定的

Proving mergesort is stable

java

sorting

mergesort