Объединить неправильный вывод

Question

У меня возникли две проблемы с моим кодом сортировки слияния в Java.

1. Когда входной массив [3,4,2,1,0,6,8], я получаю выход [0, 1, 2, 3, 4, 6, 0], что явно неверно.

2. Я подозреваю, что способ, которым я написал свой код, не так оптимален, как мог бы быть. Пожалуйста, дайте мне знать, если вы сможете найти какие-либо улучшения. Я знаю, что в Интернете существует множество алгоритмов слияния, но я спрашиваю конкретно о том, как я написал свой код. Благодаря!

   import java.util.Arrays; 
   
   public class Main { 
   
       static int[] mergeSort(int[] arr) { 
   
        if (arr == null) 
         return null; 
   
        if (arr.length <= 1) 
         return arr; 
   
        int length = arr.length; 
        int mid = arr.length/2; 
   
        int[] left = Arrays.copyOfRange(arr, 0, mid); 
        int[] right = Arrays.copyOfRange(arr, mid, length); 
   
        int[] sortedLeft = mergeSort(left); 
        int[] sortedRight = mergeSort(right); 
   
        int leftSmallestIndex = 0; 
        int rightSmallestIndex = 0; 
   
        int leftLength = left.length; 
        int rightLength = right.length; 
   
        int[] sortedArr = new int[length]; 
   
        outer: for (int i = 0; i < length; i++) { 
         if (leftSmallestIndex >= leftLength) { 
          while (rightSmallestIndex < rightLength) { 
           sortedArr[i] = sortedRight[rightSmallestIndex]; 
           rightSmallestIndex++; 
           break outer; 
          } 
         } 
         if (rightSmallestIndex >= rightLength) { 
          while (leftSmallestIndex < leftLength) { 
           sortedArr[i] = sortedLeft[leftSmallestIndex]; 
           leftSmallestIndex++; 
           break outer; 
          } 
         } 
         if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) { 
          sortedArr[i] = sortedLeft[leftSmallestIndex]; 
          leftSmallestIndex++; 
         } 
         else { 
          sortedArr[i] = sortedRight[rightSmallestIndex]; 
          rightSmallestIndex++; 
         } 
        } 
   
        return sortedArr; 
   
       } 
   
       public static void main(String[] args) { 
       // write your code here 
        int[] a = new int[] {3,4,2,1,0,6,8}; 
        System.out.println(Arrays.toString(mergeSort(a))); 
       } 
   } 
   

Answer 1

Ваша проблема в то время как петли:

while (rightSmallestIndex < rightLength) { 
       sortedArr[i] = sortedRight[rightSmallestIndex]; 
       rightSmallestIndex++; 
       break outer; 
      } 

никогда не будет цикл, потому что ваше заявление перерыв ВНУТРИ время. Кроме того, вы не увеличиваете i внутри времени, так что даже если он циклично, оно будет перезаписывать значения в текущем индексе вместо заполнения остальной части массива

меняющихся их

 if (leftSmallestIndex >= leftLength) { 
      while (rightSmallestIndex < rightLength) { 
       sortedArr[i] = sortedRight[rightSmallestIndex]; 
       rightSmallestIndex++; 
       i++; 
      } 
       break outer; 

     } 
     if (rightSmallestIndex >= rightLength) { 
      while (leftSmallestIndex < leftLength) { 
       sortedArr[i] = sortedLeft[leftSmallestIndex]; 
       i++; 
       leftSmallestIndex++; 
      } 
       break outer; 

     } 
     ..rest is the same 

должен дать вам правильные результаты

что касается улучшений ...

1. не используют ярлыки и break LABEL заявления, это очень со nfusing ", вероятно, более ясны, чтобы реорганизовать эти части в свои собственные методы с указанием типов раскрытия метода, например fillInRemainingArray()

2. Я не думаю, что вам нужно сделать копии массива, вы должны иметь возможность объединиться с только один массив

Answer 2

Ваше заявление break outer; фактически вызывает контроль, чтобы выйти из за цикл, он не продолжить цикл (я предполагаю, что вы пытаетесь продолжить цикл, с помощью этого break outer; заявление).

Это вызывает цикл, чтобы обновить только один оставшийся элемент из sortedRight или sortedLeft попасть в отсортированный массив, а остальные пропускаются, это вызывает 0 в конце вашего цикла.

Вам действительно не нужно делать это, вы можете прокручивать до - leftSmallestIndex < leftLength && rightSmallestIndex < rightLength, а затем выполнять петли while, которые вы определили внутри цикла for, вне его.

Пример -

import java.util.*; 
import java.math.*; 
class a { 
    static int[] mergeSort(int[] arr) { 

     if (arr == null) 
      return null; 

     if (arr.length <= 1) 
      return arr; 

     int length = arr.length; 
     int mid = length/2; 

     int[] left = Arrays.copyOfRange(arr, 0, mid); 
     int[] right = Arrays.copyOfRange(arr, mid, length); 

     int[] sortedLeft = mergeSort(left); 
     int[] sortedRight = mergeSort(right); 

     int leftSmallestIndex = 0; 
     int rightSmallestIndex = 0; 

     int leftLength = left.length; 
     int rightLength = right.length; 

     int[] sortedArr = new int[length]; 
     int i = 0; 
     for (; leftSmallestIndex < leftLength && rightSmallestIndex < rightLength;i++) { 
      if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) { 
       sortedArr[i] = sortedLeft[leftSmallestIndex]; 
       leftSmallestIndex++; 
      } 
      else { 
       sortedArr[i] = sortedRight[rightSmallestIndex]; 
       rightSmallestIndex++; 
      } 
     } 
     while (rightSmallestIndex < rightLength) { 
      sortedArr[i] = sortedRight[rightSmallestIndex]; 
      rightSmallestIndex++; 
      i++; 
     } 
     while (leftSmallestIndex < leftLength) { 
      sortedArr[i] = sortedLeft[leftSmallestIndex]; 
      leftSmallestIndex++; 
      i++; 
     } 
     return sortedArr; 

    } 
    public static void main(String[] args) { 
    int[] a = new int[] {3,4,2,1,0,6,8}; 
     System.out.println(Arrays.toString(mergeSort(a))); 
     outer : for(int i = 0;i < 10 ; i++) { 
     while(true) { 
      System.out.println(i); 
      break outer; 
     } 
    } 
    } 
} 

В конце концов, я добавил пример (простой вариант того, что вы пытаетесь с помощью break outer; это должно помочь вам понять, что Происходило).