Блог

Итак, я работал над MergeSort для проекта Algorithm, но я столкнулся с различными проблемами, когда дело дошло до получения кода для сортировки массивов. Всякий раз, когда я генерирую строку и помещаю ее в сортировку слиянием, кажется, что она получается точно такой же. Мне нужна помощь в поиске, где ошибка в моем коде, почему это приводит меня к этому, и решение с простым, но хорошим объяснением.

Вот что я пробовал в прошлом:

1. Я пытался использовать return arr[0] вместо arr , но он выдает мне ошибку, из-за невозможности преобразования из int в int[] .
2. Я заглянул в свой класс слияния, и, кажется, там все в порядке.
3. Я обсуждал этот вопрос со своим учителем, и он говорит, что все выглядит нормально, но я знаю, что где-то должно быть что-то не так.
4. Я пытался удалить return merge(arr1, arr2) , но система выдает сообщение об ошибке, сообщающее мне, что я должен что-то вернуть.
5. Я попытался распечатать массивы по отдельности, но он по-прежнему не показывает изменений и является точно таким же, как исходная строка.

Метод слияния:

 private static int[] merge(int[] a, int[] b)
{
    int[] c = new int[a.length   b.length];
    int counterA = 0;
    int counterB = 0;
    int counterC = 0;

    while (counterA != a.length amp;amp; counterB != b.length)
    {
      if (a[counterA] < b[counterB])
      {
        c[counterC] = a[counterA];
        counterA  ;
        counterC  ;
      }
      else
      {
        c[counterC] = b[counterB];
        counterB  ;
        counterC  ;
      }
    }

    while (counterB == b.length amp;amp; counterA != a.length)
    {
      c[counterC] = a[counterA];
      counterA  ;
      counterC  ;
    }

    while (counterA == a.length amp;amp; counterB != b.length)
    {
      c[counterC] = b[counterB];
      counterB  ;
      counterC  ;
    }

    return c;
}
  

Метод сортировки слиянием:

 public static int[] mergeSort(int[] arr)
{ 
    if (arr.length == 1)
    {
      return arr[0];
    }

    int[] arr1 = new int[arr.length / 2];
    int[] arr2 = new int[arr.length - arr1.length];

    for (int i = 0; i < arr1.length; i  )
    {
      arr1[i] = arr[i];
    }

    for (int i = 0; i < arr2.length; i  )
    {
      arr2[i] = arr[i   arr1.length];
    }

    arr1 = mergeSort(arr1);
    arr2 = mergeSort(arr2);

    return merge(arr1, arr2);
}
  

Поскольку массив генерируется случайным образом, примером может быть это:

 9, 1, 7, 5, 7, 2, 2, 9, 8, 9
  

Предполагаемый результат должен быть таким:

 1, 2, 2, 5, 7, 7, 8, 9, 9, 9
  

Однако вместо этого выводится вот что (массив получается без изменений):

 9, 1, 7, 5, 7, 2, 2, 9, 8, 9 
  

В вашем коде 2 проблемы:

• вы возвращаете элемент массива arr[0] вместо самого массива arr
• вы не обрабатываете случай arr.length == 0 . Он также должен вернуться arr .

Обратите внимание, что код может быть упрощен:

• вы можете использовать оператор для значений индекса при копировании значений,
• вам следует удалить избыточные тесты во втором и третьем while циклах.

Вот улучшенная версия:

 private static int[] merge(int[] a, int[] b)
{
    int[] c = new int[a.length   b.length];
    int counterA = 0;
    int counterB = 0;
    int counterC = 0;

    while (counterA != a.length amp;amp; counterB != b.length)
    {
        if (a[counterA] <= b[counterB])
            c[counterC  ] = a[counterA  ];
        else
            c[counterC  ] = b[counterB  ];
    }

    while (counterA != a.length)
        c[counterC  ] = a[counterA  ];

    while (counterB != b.length)
        c[counterC  ] = b[counterB  ];

    return c;
}

public static int[] mergeSort(int[] arr)
{ 
    if (arr.length < 2)
        return arr;

    int[] arr1 = new int[arr.length / 2];
    int[] arr2 = new int[arr.length - arr1.length];

    for (int i = 0; i < arr1.length; i  )
        arr1[i] = arr[i];

    for (int i = 0; i < arr2.length; i  )
        arr2[i] = arr[i   arr1.length];

    arr1 = mergeSort(arr1);
    arr2 = mergeSort(arr2);

    return merge(arr1, arr2);
}
  

Единственная проблема, которую я вижу в коде, — это return arr[0]; вместо return arr; или return new int[]{arr[0]}; в сортировке слиянием.

Помимо этого, код работает так, как ожидалось.

Если вы не видите правильный вывод, вы, вероятно, неправильно используете вывод.

Вот пример того, как я это тестировал.

     public static void main(String[] args) {

        int[] input = new int[]{9, 1, 7, 5, 7, 2, 2, 9, 8, 9};
        int[] output = mergeSort(input);
    }
  

Ваш код не компилируется так, как написано. В mergeSort , если длина массива равна 1, она должна return arr . После этого изменения ваш код работает нормально.

Однако мы можем внести несколько небольших изменений в ваш код, чтобы сделать его более чистым. Обратите внимание, что для вашего последнего цикла while в merge проверка counterA == a.length всегда будет true. Следовательно, мы можем удалить это. Кроме того, увеличение счетчиков может быть выполнено при доступе к массиву. Объединение этих предложений приводит к следующему коду для вашего merge метода:

 private static int[] merge(int[] a, int[] b)
{
    int[] c = new int[a.length   b.length];
    int counterA = 0;
    int counterB = 0;
    int counterC = 0;

    while(counterA != a.length amp;amp; counterB != b.length)
    {
        if(a[counterA] < b[counterB])
            c[counterC  ] = a[counterA  ];
        else
            c[counterC  ] = b[counterB  ];
    }

    while(counterB == b.length amp;amp; counterA != a.length)
        c[counterC  ] = a[counterA  ];

    while(counterB != b.length)
        c[counterC  ] = b[counterB  ];

    return c;
}