正确的 Mergesort 实现？

Question

我当时在做 MergeSort，我写了这段代码。问题是，我不确定我的实现是否正是该算法应该工作的方式。根据我的阅读，列表被分成两半，直到所有列表的大小为 1，然后将排序后的列表同时放在一起。例如，{2,4,1,5,8,7,6,3} 应该分解为 {2,4,1,5} 和 {8,7,6,3} 那么这两个应该进一步同时分解为 {2,4}、{1,5}、{8,7} 和 {6,3}，依此类推。然而，在我的代码中，{2,4,1,5} 被分解成它的组件，然后在另一个数组 ({8,7,6,3}) 被分解之前完全排序。我想不出有什么方法可以同时处理两个阵列。我的代码似乎工作正常，但问题是：这段代码是 MergeSort 的有效实现吗？

public static void mergesort(int[] arr)
{
    if(arr.length == 1)
        return;
    int[] arr1 = new int[arr.length/2];
    int[] arr2 = new int[arr.length - arr1.length];
    int i = 0;
    for(int j = 0; j < arr1.length; j++, i++)
    {
        arr1[j] = arr[i];
    }
    for(int j = 0; j < arr2.length; j++, i++)
    {
        arr2[j] = arr[i];
    }
    mergesort(arr1);
    mergesort(arr2);
    int x = 0, y = 0, z = 0;
    while(x < arr1.length && y < arr2.length)
    {
        if(arr1[x] < arr2[y])
        {
            arr[z] = arr1[x];
            x++;
            z++;
        }
        else
        {
            arr[z] = arr2[y];
            y++;
            z++;
        }
    }
    if(x != arr1.length)
    {
        while(x < arr1.length)
        {
            arr[z] = arr1[x];
            x++;
            z++;
        }
    }
    else if(y != arr2.length)
    {
        while(y < arr2.length)
        {
            arr[z] = arr2[y];
            y++;
            z++;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {2,4,1,5,8,7,6,3};
    mergesort(arr);
    for(int i = 0; i < arr.length; i++)
    {
        System.out.print(arr[i] + " ");
    }
}

Answer 1

离开你的问题，没有深入分析你的代码...

基本上是的。没有必要同时在两半上工作。事实上，你甚至可以在看下半部之前就完全排序上半部。这不会影响算法的正确性。

稍微不同的是，如果你想让它更高效（即同时对每个独立的一半进行排序），那么你将不得不使用多线程，这手工编码要困难得多。

（如果这是一门基础算法课程，您可能不需要知道如何制作多线程 MergeSort，因为这将涉及许多与并发/同步/线程池，这是一个完全不同的话题）

正确的 Mergesort 实现？

Correct Mergesort implementation?

java

sorting

mergesort