-3

好的，我知道这个问题并没有显示出研究工作，但是我已经多次浏览了这段代码，但我不知道我做错了什么。我知道有很多 Mergesort 实现示例，但我想按照我的方式来做。任何帮助表示赞赏，谢谢。

import java.util.Scanner;
public class MergeSort
{
    public static int[] mergeSort(int[] arr)
    {
        if (arr.length > 1)
        {
            int[] arr1 = splitLeft(arr);
            int[] arr2 = splitRight(arr);
            arr1 = mergeSort(arr1);
            arr2 = mergeSort(arr2);
            return merge(arr1, arr2);
        }
        else
            return arr;
    }

    public static int[] splitLeft(int[] arr)
    {
        int middle = arr.length / 2;
        int[] newarr = new int[middle];
        for (int i = 0; i < middle; i++)
            newarr[i] = arr[i];
        return newarr;
    }

    public static int[] splitRight(int[] arr)
    {
        int middle = arr.length / 2;
        int[] newarr = new int[arr.length - middle];
        for (int i = 0; i + middle < arr.length; i++)
            newarr[i] = arr[i + middle];
        return newarr;
    }

    public static int[] merge(int[] arr1, int[] arr2)
    {       
        int[] sorted = new int[arr1.length+arr2.length];

        int i1 = 0;
        int i2 = 0;
        int i = 0;

        while (i1 < arr1.length && i2 < arr2.length)
        {
            if (arr1[i1] < arr2[i2])
            {
                sorted[i] = arr1[i1];
                i1++;
            }

            else
            {
                sorted[i] = arr2[i2];
                i2++;
            }
        i++;
        }

        while (i1 < arr1.length) 
        {
            sorted[i] = arr1[i1];
            i1++;
            i++;
        }

        while (i2 < arr2.length) 
        {
            sorted[i] = arr1[i2];
            i2++;
            i++;
        }
        return sorted;
    }

    public static int getNum(int x)
    {
        int num = (int)(Math.random()*x + 1);
        return num;
    }

    public static void printArr(int[] arr)
    {
        System.out.println();
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
    }

    static Scanner reader = new Scanner(System.in);
    public static void main(String [ ] args)
    {
        int i;

        System.out.println("Type the length of the array");
        int n = reader.nextInt();

        System.out.println("Type the range of the random numbers generator");
        int range = reader.nextInt();

        int[]arr = new int[n];

        for (i = 0; i < n; i++)
            arr[i] = getNum(range);

        printArr(arr);

        int[] sorted = new int[n];
        sorted = mergeSort(arr);

        printArr(sorted);
    }
}
4

2 回答 2

2

我认为问题出在你的splitRight功能上。考虑这段代码：

for (int i = middle; i < arr.length; i++)
    newarr[i] = arr[i];

这试图将第ith 元素从arr的i第 th 位置复制newarr，但这是不正确的。例如，如果数组arr有 10 个元素，您希望将元素 5 复制arr到 的位置 0 newArr，将元素 6复制arr到 的位置 1 newarr，等等。

要解决此问题，请考虑尝试以下操作：

for (int i = 0; i + middle < arr.length; i++)
    newarr[i] = arr[i + middle];

希望这可以帮助！

于 2012-07-09T20:35:45.923 回答
0

当你这样做

for (int i = middle; i < arr.length; i++)
            newarr[i] = arr[i];

您肯定是在询问原始数组中的位置，同时在新数组中寻找它们（恰好更短）。

于 2012-07-09T20:36:20.980 回答