合并排序算法合并功能不起作用

Question

我正在尝试制作我自己的合并排序版本，但是，我对如何将两个数组合并回具有顺序顺序的单个数组有些困惑。

下面是我的代码，在我尝试运行程序后，弹出一些对我来说没有意义的数字，比如776247896 327641 57752310。

谁能告诉我我的代码出了什么问题？请赐教。非常感谢。

//nL is the length of left[]
//nR is the length of right[]
//nA is the length of A[]

void merge(int left[], int nL, int right[], int nR, int A[], int nA) {
    int temp[nA];
    
    int i = 0, j = 0, k = 0;
    
    while (i < nL && j < nR) {
        if (left[i] <= right[j]) {
            temp[k++] = left[i++];
        }
        else if (left[i] > right[j]) {
            temp[k++] = right[j++];
        }
    }
    
    while (i == nL && j < nR && k < nA) {
        temp[k++] = right[j++];
    }
    while (j == nR && i < nL && k < nA) {
        temp[k++] = left[i++];
    }
    
    for (int m = 0; m < nA; m++) {
        temp[m] = A[m];
    }
}

int main(void) {
    int left[4] = { 13, 22, 25, 60};
    int right[4] = { 9, 11, 27, 55};
    int sorted[8];
    
    merge(left, 4, right, 4, sorted, 8);
    
    for (int i = 0; i < 8; i++) {
        printf("%i\n", sorted[i]);
    }
}

Answer 1

不应该反过来吗？

   temp[m] = A[m];

因此你的数组 A 充满了存储在堆栈中的随机字节。

Answer 2

merge 函数中的最终循环不会从 temp 复制回 A，而是相反。应该改为：

    for (int m = 0; m < nA; m++) {
        A[m] = temp[m];
    }

另请注意这些备注：

目标数组的长度应该是左右数组长度之和，不需要指定。
测试else if (left[i] > right[j])是多余的，应该删除。
测试 while (i == nL && j < nR && k < nA) 也是多余的：在第一个循环结束时，i == nL 或 j == nR 或两者都有。你可以简单地写 while (j < nR) 并且下面的循环也可以简化。

这是修改后的版本：

#include <stdio.h>

//nL is the length of left[]
//nR is the length of right[]
//nA is the length of A[]

void merge(int left[], int nL, int right[], int nR, int A[]) {
    int temp[nL + nR];
    
    int i = 0, j = 0, k = 0;
    
    while (i < nL && j < nR) {
        if (left[i] <= right[j]) {
            temp[k++] = left[i++];
        } else {
            temp[k++] = right[j++];
        }
    }
    
    while (i < nL) {
        temp[k++] = left[i++];
    }
    while (j < nR) {
        temp[k++] = right[j++];
    }
    
    for (int m = 0; m < k; m++) {
        A[m] = temp[m];
    }
}

int main(void) {
    int left[4] = { 13, 22, 25, 60};
    int right[4] = { 9, 11, 27, 55};
    int sorted[8];
    
    merge(left, 4, right, 4, sorted);
    
    for (int i = 0; i < 8; i++) {
        printf("%i\n", sorted[i]);
    }
}

合并排序算法合并功能不起作用

mergesort algorithm merge function doesnt work

sorting

algorithm

merge

mergesort