创建递归合并排序方法

Question

我目前正在尝试实现合并排序方法来对充满随机数的数组进行排序。 main 方法告诉数组是否已正确排序。

到目前为止，我已经尽我所能编写了该方法，但无论我尝试什么，我都无法理解为什么我的合并排序不起作用。我不太了解合并排序，因此感谢任何帮助

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args)
    {
        int[] start = new int[100];
        for(int i = 0; i < start.length; i++)
        {
            start[i] = (int)(Math.random()*20 + 1);
        }
        int[] sorted = Arrays.copyOf(start,start.length);
        Arrays.sort(sorted);
        mergesort(start);
        if(Arrays.equals(start, sorted))
            System.out.print("correctly sorted");
        else
            System.out.print("not properly sorted");
    }
    
    
    public static void mergesort(int[] arr)
    {
        //base case then general case
        //all merging code, no sorting

        //base case
        if(arr.length ==0 || arr.length < 2 || arr.length <=1)
        {
            return;
        }
        //divide
            int half = arr.length/2;
            int[]arr1 = new int[half];
            for(int i =0; i<half; i++)
            {
                arr1[i] = arr[i];
            }
            int[]arr2 = new int[arr.length - half];
            for(int i =half; i<arr.length; i++)
            {
                arr2[i-half]= arr[i];
            }

            //merging
            int[]merge = new int[arr1.length+arr2.length];

            int k = 0;
            int i=0;
            int j=0;
            while(i<arr1.length && j<arr2.length)
                {
                    if(i<arr1.length && (j>=arr2.length || arr1[i]<=arr2[j]))
                    {
                        merge[k++] = arr1[i++];
                    }
                    else
                    {
                        merge[k++] = arr2[j++];
                    }
                }
            
                while(i<arr1.length)
                {
                    merge[k++] = arr1[i++];
                }

                while(j<arr2.length)
                {
                    merge[k++] = arr2[j++];
                }


        
        
    }

}

每次运行代码时，我总是得到“未正确排序”

Answer 1

您的合并条件不正确。

您正在使用“我”

在填充'arr2'的第二个for循环中，您使用的是arr2[i-half] = arr[i]，它应该是arr2[i-half] = arr[i]

这是更正后的代码

public class MergeSort {

    public static void main(String[] args)
    {
        int[] start = new int[100];
        for(int i = 0; i < start.length; i++)
        {
            start[i] = (int)(Math.random()*20 + 1);
        }
        int[] sorted = Arrays.copyOf(start,start.length);
        Arrays.sort(sorted);
        mergesort(start);
        if(Arrays.equals(start, sorted))
            System.out.print("correctly sorted");
        else
            System.out.print("not properly sorted");
    }
    
    
    public static void mergesort(int[] arr)
    {
        // base case
        if(arr.length <= 1)
        {
            return;
        }
        
        // divide
        int half = arr.length / 2;
        int[] arr1 = Arrays.copyOfRange(arr, 0, half);
        int[] arr2 = Arrays.copyOfRange(arr, half, arr.length);

        // recursive calls
        mergesort(arr1);
        mergesort(arr2);

        // merge
        int i = 0, j = 0, k = 0;
        while(i < arr1.length && j < arr2.length)
        {
            if(arr1[i] <= arr2[j])
            {
                arr[k++] = arr1[i++];
            }
            else
            {
                arr[k++] = arr2[j++];
            }
        }

        while(i < arr1.length)
        {
            arr[k++] = arr1[i++];
        }

        while(j < arr2.length)
        {
            arr[k++] = arr2[j++];
        }
    }
}

希望我能够解决您的问题，如果是这样，请投票并继续编码！！