Почему этот метод неправильно сортирует массивы по большим числам?

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)

Возвращает экземпляр Integer, представляющий указанное значение int.Если новый экземпляр Integer не требуется, этот метод обычно следует использовать в предпочтении перед конструктором Integer(int), поскольку этот метод может значительно повысить производительность пространства и времени за счет кэширования часто запрашиваемых значений.Этот метод всегда будет кэшировать значения в диапазоне от -128 до 127 включительно и может кэшировать другие значения вне этого диапазона.

Вероятно, можно с уверенностью предположить, что этот метод используется, когда 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)

---

Sideпримечание: хотя симметрия хороша, я бы действительно подумал об использовании < (или >) вместо этой 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++;
  }
}

Answer 2

== на объекте Integer вызывал проблему.Найти модифицированную версию кода.

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++) {
            if (nums1First >= nums1.length) {
                nums[i] = nums2[nums2First];
                nums2First++;
            } else if (nums2First >= nums2.length) {
                nums[i] = nums1[nums1First];
                nums1First++;
            } else {
                nums[i] = Math.min(nums1[nums1First], nums2[nums2First]);

                if (nums[i].equals (nums1[nums1First])) {
                    nums1First++;
                } 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; i++) {
            System.out.print(testMerge[i] + ", ");
        }
    }
}

Вывод: