java - 为什么此方法不能正确地对较大数字的数组进行排序？

Question

我是 Java 的新手，目前正在学习排序算法。我在制作自己的归并排序算法时遇到了一个奇怪的问题。我在下面为我的 mergeArrays 方法(应该合并和排序两个排序数组)添加了我的代码，问题是它适用于较小的数字，例如{9, 13, 89, 199} 和 {1, 89, 127}，但它不适用于更大的，例如{9, 13, 89, 5000} 和 {1, 89, 5001}，因为它最终重复第二大数字，即它输出 {1, 9, 13, 89, 5000, 5000} 而不是 {1, 9, 13、89、5000、5001}。我只是不明白为什么会这样，如果有人能提供帮助，我将不胜感激!

谢谢!

import java.util.*;

public class MergeSortExample
{
  public Integer[] mergeArrays (Integer[] nums1, Integer[] nums2)
  {
    Integer[] nums = new Integer[nums1.length + nums2.length];

    int nums1First = 0, nums2First = 0;
    for (int i = 0; i < nums.length; i++)
    {
      nums[i] = Math.min (nums1[nums1First], nums2[nums2First]);
      if (nums[i] == nums1[nums1First])
      {
        if (nums1First == nums1.length - 1)
        {
          nums1[nums1First] = Integer.MAX_VALUE;
        }
        else
        {
          nums1First++;
        }
      }
      else if (nums[i] == nums2[nums2First])
      {
        if (nums2First == nums2.length - 1)
        {
          nums2[nums2First] = Integer.MAX_VALUE;
        }
        else
        {
          nums2First++;
        }
      }
    }
    return nums;
  }

  public static void main (String[] args)
  {
    /*Integer[] num1 = {9, 13, 89, 5000};
      Integer[] num2 = {1, 89, 5001}; does not work*/

    Integer[] num1 = {9, 13, 89, 199}; //works
    Integer[] num2 = {1, 89, 127}; //works

    MergeSortExample m = new MergeSortExample ();
    Integer[] testMerge = m.mergeArrays (num1, num2);

    for (int i = 0; i < testMerge.length - 1; i++)
    {
      System.out.print (testMerge[i] + ", ");
    }
    System.out.println (testMerge[testMerge.length - 1]);   
  }
}    

Answer 1

Integer意味着有一个对象。将对象与 == 进行比较时通常它们是不等价的，想想常见的错误 String -s.
它适用于小数字的原因是它们被缓存，有一个针对小整数的预实例化集，在 valueOf(int i) 中描述。 :

public static Integer valueOf(int i)

Returns an Integer instance representing the specified int value. If a new Integer instance is not required, this method should generally be used in preference to the constructor Integer(int), as this method is likely to yield significantly better space and time performance by caching frequently requested values. This method will always cache values in the range -128 to 127, inclusive, and may cache other values outside of this range.

可以安全地假设当 Java 自动装箱时使用此方法 int -s 进入 Integer -s.

解决方案:不要那样做，使用int阵列。然后它会突然起作用。

您可以尝试的简单测试代码:

Integer a127=127;
Integer b127=127;
Integer a5000=5000;
Integer b5000=5000;
System.out.println(a127+"=="+b127+"? "+(a127==b127));
System.out.println(a5000+"=="+b5000+"? "+(a5000==b5000));

(查看它在 Ideone 上的运行情况:https://ideone.com/vEry18)

---

旁注:虽然对称性很好，但我真的会考虑使用 < (或 > )而不是 Math.min()魔法，即使它导致写作 nums[i] =两次:

if (nums1[nums1First] < nums2[nums2First])
{
  nums[i] = nums1[nums1First];
  if (nums1First == nums1.length - 1)
  {
    nums1[nums1First] = Integer.MAX_VALUE;
  }
  else
  {
    nums1First++;
  }
}
else
{
  nums[i] = nums2[nums2First];
  if (nums2First == nums2.length - 1)
  {
    nums2[nums2First] = Integer.MAX_VALUE;
  }
  else
  {
    nums2First++;
  }
}