合并排序代码未提供所需的输出

Question

刚开始学习递归。问题是合并排序，我试图在不打破两个数组的情况下解决它，所以我传递了开始索引 (si) 和结束索引 (end)。

    #include <iostream>
    using namespace std;

void inputArray(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
}

void printArray(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

void mergeArray(int a[], int si, int end)
{
    int mid = (si + end) / 2;
    int size = end - si + 1;
    int temp[size];
    int index = 0, i = si, j = mid + 1;

    while (i <= mid && j <= end)
    {
        if (a[i] <= a[j])
        {
            temp[index] = a[i];
            index++;
            i++;
        }
        else
        {
            temp[index] = a[j];
            index++;
            j++;
        }
    
    }

    if (i > mid)
    {
        while (j <= end)
        {
            temp[index] = a[j];
            index++;
            j++;
        }
    }
    if (j > end)
    {
        while (i <= mid)
        {
            temp[index] = a[i];
            index++;
            i++;
        }
    }
    //Copying Content Of Temp Array Back To Original Array
    int k=0;
    for (i = si; i < size; i++)
    {
        a[i] = temp[k];
        k++;
    }

}

void mergeSort(int a[], int si, int end)
{
    if (si >= end)
    {
        return;
    }

    int mid = (si + end) / 2;
    mergeSort(a, si, mid);
    mergeSort(a, mid + 1, end);
    mergeArray(a, si, end);
}

int main()
{
    int a[100];
    int n;
    cin >> n;
    inputArray(a, n);
    mergeSort(a, 0, n - 1);
    printArray(a, n);

    return 0;
}

抱歉，代码太长，它在以下情况下失败：6 5 4 3（按降序排列）但适用于其他情况，例如 6 5 4 9

我从昨天开始尝试调试这段代码，有人可以帮我吗

Answer 1

void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1, n2 = end - mid, a1[n1], a2[n2];
    
    for(int i = 0; i < n1; ++i) a1[i] = arr[i + start];
    for(int i = 0; i < n2; ++i) a2[i] = arr[mid + 1 + i];
    
    int i = 0, j = 0, k = start;
    
    while(i < n1 && j < n2) {
        if(a1[i] < a2[j]) {
            arr[k++] = a1[i++];
        }
        else arr[k++] = a2[j++];
    }
    
    if(i < n1) arr[k++] = a1[i++];
    if(i < n2) arr[k++] = a2[j++];
}

void mergeSort(int *arr, int start, int end) {
    if(start >= end) return;
    int mid = start + (end - start) / 2;
    
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}

试试这个逻辑

Answer 2

已修复，谢谢大家！

      #include <iostream>
    using namespace std;
    
    void inputArray(int a[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }
    
    void printArray(int a[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    
    void mergeArray(int a[], int si, int end)
    {
        int mid = (si + end) / 2;
        int size = end - si + 1;
        int temp[size];
        int index = 0;
        int i = si;
        int j = mid + 1;
    
        while (i <= mid && j <= end)
        {
            if (a[i] <= a[j])
            {
                temp[index] = a[i];
                index++;
                i++;
            }
            else
            {
                temp[index] = a[j];
                index++;
                j++;
            }
        }
    
        while (j <= end)
        {
            temp[index] = a[j];
            index++;
            j++;
        }
    
        while (i <= mid)
        {
            temp[index] = a[i];
            index++;
            i++;
        }
    
        index = 0;
        for (i = si; i <= end; i++)
        {
            a[i] = temp[index];
            index++;
        }
    }
    
    void mergeSort(int a[], int si, int end)
    {
        if (si >= end)
        {
            return;
        }
    
        int mid = (si + end) / 2;
        mergeSort(a, si, mid);
        mergeSort(a, mid + 1, end);
        mergeArray(a, si, end);
    }
    
    int main()
    {
        int a[100];
        int n;
        cin >> n;
        inputArray(a, n);
        mergeSort(a, 0, n - 1);
        printArray(a, n);
    
        return 0;
    }

合并排序代码未提供所需的输出

Merge Sort Code Not Giving Desired Output

c++

mergesort