部分递归调用mergeSort期间合并排序的无限循环问题

Question

我正在做一项家庭作业，比较执行时间和 10 种不同类型的理论 O 表示法。但是，正如问题所说，当我到达代码递归调用合并排序的地步时，我一直在无限循环。我知道是当左边在 2 右边在 3 时，所以中间连续 returns 作为 3。合并应该在 if 语句之外吗？我也不认为这是正确的，但当我看到它时。

void merge(int arr[], int left, int middle, int right)
{
    // get the temporary array lengths
    int first = middle - left + 1;
    int second = right - middle;

    // make the temp dynamic arrays
    int *Left = new int(first);
    int *Right = new int(second);
    for (int i = 0; i < first; i++)
    {
       Left[i] = arr[left + i];
    }
    for (int i = 0; i < second; i++)
    {
        Right[i] = arr[middle + 1 + i];
    }

    // merge the arrays back into arr
    int i = 0;
    int j = 0;
    int k = left;

    while (i < first && j < second)
    {
        // check which one is bigger
        if (Left[i] <= Right[j])
        {
            arr[k] = Left[i];
            i++;
        }
        else
        {
            arr[k] = Right[j];
            j++;
        }
        k++;
    }
    // copy Left remainder
    while (i < first)
    {
        arr[k] = Left[i];
        i++;
        k++;
    }
    // copy right remainder
    while (j < second)
    {
        arr[k] = Right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int middle = left + (right - 1) / 2;
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

Answer 1

在mergeSort函数中，你在计算middle时忘记了括号。应该是：

int middle = (left + (right - 1)) / 2;

此外，在 merge 函数中，Left 和 Right 的类型应为 int[]。您应该使用 new int[SIZE] 而不是 new int(SIZE)。此外，在离开函数之前，您应该使用delete[]删除它们以防止内存泄漏。

// make the temp dynamic arrays
int* Left = new int[first];
int* Right = new int[second];

// ...

// at the end of the `merge` function
delete[] Left;
delete[] Right;

部分递归调用mergeSort期间合并排序的无限循环问题

Infinite loop problem with the merge sort during the portion recursively calls mergeSort

c++

mergesort

infinite-loop