0

首先，我想从我的方法背后的推理开始。我的想法是我将输入一个偶数或奇数的数组。该数组将被分解为一个二维数组，其长度为原始数组的长度，每个索引都有一个大小为 1 的数组。然后我将继续将索引合并在一起。这适用于大小为 2、4、8、16 的长度。现在，我不得不稍微编辑我的方法，因为 3、5、6、7 不起作用。现在，我的问题是即使它们有效，但并非所有案例都有效。例如，长度 25 不能正确返回。下面是我的代码：

/**
* A method to perform a merge sort
* @param array The array being fed in
*/
public static int[] mergeSort(int[] array)
{
  if (array.length == 1)
  {
     return array;
  }

  int size = array.length;
  int[][] miniArrayList = new int[size][1];

  for (int index = 0; index < array.length; index++)
  {
     miniArrayList[index][0] = array[index];
  }

  while (miniArrayList.length > 1)
  {
     if (miniArrayList.length % 2 == 0)
     {
        miniArrayList = mergeEven(miniArrayList);
     }
     else
     {
        miniArrayList[0] = mergeOdd(miniArrayList);
     }
  }
  return miniArrayList[0];
}

我对上述方法的想法是，我输入一个数组，将其分解，然后一点一点地合并数组，直到我有一个大小为 1 的排序数组。上面的方法调用以下方法：

private static int[][] mergeEven(int[][] array)
{
  int[][] tempSortList = new int[array.length / 2][];
  int tempIndex = 0;
  for (int index = 0; index < array.length; index += 2)
  {
     tempSortList[tempIndex] = merge(array[index], array[index + 1]);
     if (tempIndex != tempSortList.length)
     {
        tempIndex++;
     }
  }
  array = tempSortList;
  return array;
}

private static int[] mergeOdd(int[][] array)
{
  /**
   * The concept is to call the even merge method on the even part
   * of the list and then once I get to one array, I merge that array
   * with the extra array.
   */
  int[][] localArray = new int[array.length - 1][1];
  int[][] extra = new int[1][1];

  for (int index = 0; index < localArray.length; index++)
  {
     localArray[index][0] = array[index][0];
  }

  extra[0][0] = array[array.length - 1][0];

  int[][] tempSortList = new int[localArray.length / 2][];
  int tempIndex = 0;
  for (int index = 0; index < localArray.length; index += 2)
  {
     tempSortList[tempIndex] = merge(localArray[index], localArray[index + 1]);
     if (tempIndex != tempSortList.length)
     {
        tempIndex++;
     }
  }
  localArray = tempSortList;

  return localArray[0] = merge(localArray[0], extra[0]);
}

这是不言自明的，但以防万一。由于数组是奇数或偶数，因此上述方法的排序方式不同。最后，这些方法调用实际的合并方法（我认为这可行）：

/**
* A merge method to merge smaller arrays to bigger
* arrays
* @param arrayOne The first array being fed in
* @param arrayTwo The second array being fed in
* @return A new integer array which is the sum of the
* length of the two arrays
*/
private static int[] merge(int[] arrayOne, int[] arrayTwo)
{
  /*
   * To make a proper method that deals with odd array sizes
   * look into seeing if it odd, only merging length of the array -1
   * and then once that is all merged merge that array with the last part of the array
   */
  //Creating the size of the new subarray
  int[] mergedArray;

  if (arrayOne.length % 2 == 0 && arrayTwo.length % 2 == 0)
  {
     int size = arrayOne.length;
     int doubleSize = 2 * size;
     mergedArray = new int[doubleSize];

     //Positions of each array
     int posOne = 0;
     int posTwo = 0;
     int mergeIndex = 0;

     while (posOne < size && posTwo < size)
     {
        if (arrayOne[posOne] < arrayTwo[posTwo])
        {
           mergedArray[mergeIndex] = arrayOne[posOne];
           mergeIndex++;
           posOne++;
        }
        else
        {
           mergedArray[mergeIndex] = arrayTwo[posTwo];
           mergeIndex++;
           posTwo++;
        }
     }

     if (posOne == size)
     {
        for (int rest = posTwo; rest < size; rest++)
        {
           mergedArray[mergeIndex] = arrayTwo[rest];
           mergeIndex++;
        }
     }
     else
     {
        for (int rest = posOne; rest < size; rest++)
        {
           mergedArray[mergeIndex] = arrayOne[rest];
           mergeIndex++;
        }
     }

  }
  else
  {
     int arrayOneSize = arrayOne.length;
     int arrayTwoSize = arrayTwo.length;
     int newArraySize = arrayOneSize + arrayTwoSize;
     mergedArray = new int[newArraySize];

     //Position in each array
     int posOne = 0;
     int posTwo = 0;
     int mergeIndex = 0;

     while (posOne < arrayOneSize && posTwo < arrayTwoSize)
     {
        if (arrayOne[posOne] < arrayTwo[posTwo])
        {
           mergedArray[mergeIndex] = arrayOne[posOne];
           mergeIndex++;
           posOne++;
        }
        else
        {
           mergedArray[mergeIndex] = arrayTwo[posTwo];
           mergeIndex++;
           posTwo++;
        }
     }
     if (posOne == arrayOneSize)
     {
        mergedArray[mergeIndex] = arrayTwo[posTwo];
        mergeIndex++;
     }
     else
     {
        for (int rest = posOne; rest < arrayOneSize; rest++)
        {
           mergedArray[mergeIndex] = arrayOne[rest];
           mergeIndex++;
        }
     }

  }

  return mergedArray;
}

所以我的问题是，我正确输入的任何数组大小，它只适用于某些大小。我已经阅读了一些文章，但我的实现与我所看到的大多数情况截然不同，这就是我在这里发布的原因。我不想只是复制一个工作的，我想了解我做错了什么，以便我可以修复它。提前感谢您的帮助！

4

2 回答 2

0

Your bigger problem is that your algorithm is way too complicated, not to mention inefficient for really large arrays.

I'm assuming you're doing this as an academic exercise, but whenever you get it working check out java.util.Arrays.mergeSort (private method) for an example.

于 2013-04-22T13:41:44.217 回答
0

你的问题在逻辑上merge。通过使用线

int size = arrayOne.length;

您假设两个数组的长度相同。但是，在不均匀的情况下，并非所有数组都具有相同的长度。

将其更改为两种不同的大小，代码应该没问题。

于 2013-04-22T13:37:24.983 回答