java - 我的mergesort代码中的merge函数怎么了？

抱歉，初学者在这里。这就是我现在所拥有的：

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

private static void sort(int[] arr, int lo, int hi)
{
    if(lo >= hi)
    {
        return;
    }
    int mid = (lo + hi)/2;

    sort(arr, lo, mid);
    sort(arr, mid + 1, hi);

    int size = hi - lo + 1;
    int[] temp = new int[size]; //new array to merge into

    merge(arr, temp, lo, mid + 1, hi);

    for(int i = 0; i < size; i++)
    {
        arr[i + lo] = temp[i];
    }
}

private static void merge(int[] arr, int[] temp, int lower, int mid, int upper)
{
    int tempIndex = 0;
    int leftLo = lower;
    int leftHi = mid - 1;
    int rightLo = mid;
    int rightHi = upper;

    while(leftLo <= leftHi && rightLo <= rightHi)
    {
        if(arr[leftLo] < arr[rightLo])
        {
            temp[tempIndex] = arr[leftLo];
            tempIndex++;
            leftLo++;
        }
        else
        {
            temp[tempIndex] = arr[rightLo];
            tempIndex++;
            rightLo++;
        }
    }
}
 }

我知道这是合并功能无法正常工作的原因，因为现在它仅打印出最小的元素，其余的都打印为0。我认为这与需要另一个while循环来复制数组有关，但是我不知道如何写，甚至不知道它的目的，因为现在看来该数组正在合并到temp数组中以正确的顺序。为什么只正确打印第一个元素？谢谢。

最佳答案

在merge中，只要leftLo和rightLo都尚未达到其极限，就可以复制值。通常其中之一会提前到达。然后，您需要复制另一个值的剩余值。您可以通过添加以下两个循环来复制其余元素：

    while (leftLo <= leftHi) {
        temp[tempIndex] = arr[leftLo];
        tempIndex++;
        leftLo++;
    }
    while (rightLo <= rightHi) {
        temp[tempIndex] = arr[rightLo];
        tempIndex++;
        rightLo++;
    }

也就是说，完整的方法变为：

private static void merge(int[] arr, int[] temp, int lower, int mid, int upper) {
    int tempIndex = 0;
    int leftLo = lower;
    int leftHi = mid - 1;
    int rightLo = mid;
    int rightHi = upper;

    while (leftLo <= leftHi && rightLo <= rightHi) {
        if (arr[leftLo] < arr[rightLo]) {
            temp[tempIndex] = arr[leftLo];
            tempIndex++;
            leftLo++;
        } else {
            temp[tempIndex] = arr[rightLo];
            tempIndex++;
            rightLo++;
        }
    }
    while (leftLo <= leftHi) {
        temp[tempIndex] = arr[leftLo];
        tempIndex++;
        leftLo++;
    }
    while (rightLo <= rightHi) {
        temp[tempIndex] = arr[rightLo];
        tempIndex++;
        rightLo++;
    }
}

关于java - 我的mergesort代码中的merge函数怎么了？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34276420/