-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];

iこれは から 番目の要素arrを のi番目の位置にコピーしようとしますnewarrが、これは正しくありません。たとえば、配列に 10 個の要素がある場合、 の要素 5を の位置 0 に、 の要素 6を の位置 1などarrにコピーします。arrnewArrarrnewarr

これを修正するには、次のようなことを試すことを検討してください。

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 に答える