证明mergesort是稳定的

Question

我写了一个mergesort算法.当我运行以下测试时:

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类,而不是原始的int,我想我可以得到hashCode()自从Integer扩展基Object类.

但是,当我尝试

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类中.如果您执行以下操作:

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

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

另外,正如评论中所建议的那样,您可以在课程中添加一个额外的字段以进行比较.

编辑:要回答您的编辑,Integer.hashcode()文档说明hascode是

等于此Integer对象表示的原始int值.