c++ - 我的 C++ 合并排序代码不起作用。我在这里缺少什么？

Question

在我的代码中，lb指下限和 ub指的是上限。我正在使用 mergeSort function递归地将数组拆分成更小的部分和 merge function以它们的排序顺序合并。

#include <iostream>
using namespace std;

void merge(int input[], int lb, int ub, int size)
{
    int i = lb;
    int k = 0;
    int mid = (lb + ub) / 2;
    int j = mid + 1;

    int *arr = new int[size];

    while (i <= mid && j <= ub)
    {
        if (input[i] <= input[j])
            arr[k++] = input[i++];
        else
            arr[k++] = input[i++];
    }
    while (i <= mid)
        arr[k++] = input[i++];
    while (j <= ub)
        arr[k++] = input[j++];

    for (k = 0; k < size; k++)
        input[k] = arr[k];
}
void mergeSort(int input[], int size)
{
    int lb = 0;
    int ub = size - 1;
    int mid;
    if (size == 0)
    {
        return;
    }
    else if (lb < ub)
    {
        mid = (lb + ub) / 2;
        mergeSort(input, mid - lb + 1);
        mergeSort(input + mid + 1, ub - mid);
        merge(input, lb, ub, size);
    }
    else
    {
        return;
    }
}

int main()
{
    int input[1000], length;
    cin >> length;
    for (int i = 0; i < length; i++)
        cin >> input[i];
    mergeSort(input, length);
    for (int i = 0; i < length; i++)
    {
        cout << input[i] << " ";
    }
}

Answer 1

您在合并函数的第一个 while 循环中使用了 i 而不是 j 。正确的代码如下

while (i <= mid && j <= ub) { 
        if (input[i] <= input[j]) 
           arr[k++] = input[i++]; 
       else 
           arr[k++] = input[j++];     
}