Реализация сортировки слиянием в Java

Question

Вот моя реализация сортировки слиянием в java

import java.io.*;
import java.util.Arrays;

public class MergeSort
{
  private static int [] LeftSubArray(int [] Array)
  {
    int [] leftHalf = Arrays.copyOfRange(Array, 0, Array.length / 2);
    return leftHalf;
  }

  private static int [] RightSubArray(int [] Array)
  {
    int [] rightHalf = Arrays.copyOfRange(Array, Array.length / 2 + 1, Array.length);
    return rightHalf;
  }

  private static int [] Sort(int [] A)
  {
    if(A.length > 1)
    {
      return Merge( Sort( LeftSubArray(A) ) , Sort( RightSubArray(A) ) );
    }
    else
    {
      return A;
    }
  }

  private static int [] Merge(int [] B, int [] C)
  {
    int [] D = new int[B.length + C.length];
    int i,j,k;
    i = j = k = 0;
    while(k < D.length)
    {
      if(i == B.length)
      {
        //Copy the remainder of C into D
        while(k < D.length){ D[k++] = C[j++]; }
      }
      if(j == C.length)
      {
        //Copy the remainder of B into D
        while(k < D.length){ D[k++] = B[i++]; }
      }
      if(i<B.length && j<C.length)
      {
        if(B[i] > C[j]){ D[k++] = B[i++]; }
        else { D[k++] = C[j++]; }
      }
    }
    return D;
  }

  public static void main(String [] args)
  {
    int [] array = {1,3,5,2,4};
    int [] sorted = MergeSort.Sort(array);
    for(int i = 0;i < sorted.length; ++i)
    {
      System.out.print(sorted[i] + " ");
    }
  }
}

Вывод, который я получаю:

2 1

Из того, что я могу сказать, кажется, проблема с моим делением правой субмассив.Что я делаю не так?

Answer 1

Вот javadoc copyOfRange:

Parameters:
original - the array from which a range is to be copied
from - the initial index of the range to be copied, **inclusive**
to - the final index of the range to be copied, **exclusive**. (This index may lie outside the array.)

Я выделил два слова, на которые стоит обратить особое внимание; -)

Answer 2

Если в вашем массиве 10 элементов, то LeftSubArray копирует элементы 0..5, а RightSubArray копирует элементы 6..10.Но если первый элемент имеет индекс 0, то нет элемента с индексом 10. И если copyOfRange (a, b) дает элементы, индексированные a..b-1, то LeftSA дает 0..4, а RightSAуступая 6..9.В любом случае, ваше предположение о делении кажется верным.

Answer 3

Я нашел точное решение в книге Роберта Седжвика «Алгоритмы на языке Java»

1. Читайте здесь о слиянии

Answer 4

Этот фрагмент кода работает: у вас было несколько ошибок: см. Следующие различия:

• метод rightSubArray
• скопируйте остаток B
• скопируйте остатокC

Код, который работает следующим образом:

public class MergeSort
{
  private static int [] LeftSubArray(int [] Array)
  {
    int [] leftHalf = Arrays.copyOfRange(Array, 0, Array.length / 2);
    return leftHalf;
  }

  private static int [] RightSubArray(int [] Array)
 {
    int[] rightHalf = Arrays.copyOfRange(Array, Array.length / 2,
            Array.length);
 return rightHalf;
 }

 private static int [] Sort(int [] A)
 {
  if(A.length > 1)
  {
    return Merge( Sort( LeftSubArray(A) ) , Sort( RightSubArray(A) ) );
  }
  else
{
  return A;
}
}

private static int [] Merge(int [] B, int [] C)
{
  int [] D = new int[B.length + C.length];
  int i,j,k;
  i = j = k = 0;
  while(k < D.length)
  {
    if(i == B.length)
    {
    //Copy the remainder of C into D
            while (j < C.length) {
                D[k++] = C[j++];
            }
  }
  if(j == C.length)
  {
    //Copy the remainder of B into D
            while (i < B.length) {
                D[k++] = B[i++];
            }
  }
        if (i < B.length && j < C.length)
  {
            if (B[i] > C[j]) {
                D[k++] = B[i++];
            } else {
                D[k++] = C[j++];
            }
  }
}
return D;
}

 public static void main(String [] args)
  {
   int [] array = {1,3,5,2,4};
   int [] sorted = MergeSort.Sort(array);
   for(int i = 0;i < sorted.length; ++i)
   {
     System.out.print(sorted[i] + " ");
   }
 }
}

Answer 5

С вашим кодом [1,3,5,2,4] делится на [1,3] и [2,4].Удачи