我的合并输出与比较和交换的测试用例不匹配

Question

我正在尝试编写一个代码来接收向量的数量、每个向量的大小以及大学作业的向量，但是当我尝试这样做时，比较的数量与应有的结果不匹配。

示例：

输入：

3
4 8 16
3 6 5 2
4 8 2 1 9 0 2 3
1 3 2 7 5 5 2 7 2 9 3 0 8 3 1 4

输出：

I 4 10 6
M 4 16 5
I 8 30 20
M 8 48 16
I 16 83 67
M 16 128 48

我的是：

I 4 10 6
M 4 16 4
I 8 30 20
M 8 48 12
I 16 83 67
M 16 128 32

代码：

#include <stdio.h>
#include <stdlib.h>

void merge(int *a, int cvetor, int fvetor, int *b, int *trocas, int *comp) {
    if (cvetor >= fvetor) {
        return;
    }
    int m = (cvetor + fvetor) / 2;
    merge(a, cvetor, m, b, trocas, comp);
    merge(a, m + 1, fvetor, b, trocas, comp);

    int i1 = cvetor;
    int i2 = m + 1;
    int j = cvetor;

    while (i1 <= m && i2 <= fvetor) {
        if (a[i1] <= a[i2]) {
            (*comp)++; 
            b[j++] = a[i1++];
        } else {
            (*comp)++; 

            b[j++] = a[i2++];
        }
        (*trocas)++; 
    }

    while (i1 <= m) {
        b[j++] = a[i1++];
        (*trocas)++; 
    }

    while (i2 <= fvetor) {
        b[j++] = a[i2++];
        (*trocas)++; 
    }

    for (int i = cvetor; i <= fvetor; i++) {
        a[i] = b[i];
        (*trocas)++; 
    }
}

void insert(int *a, int n, int *trocas, int *comp) {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = i - 1;
        (*trocas)++;
        while (j >= 0) {
            (*comp)++;
            if (a[j] > x) {
                a[j + 1] = a[j];
                j--;
                (*trocas)++; 
            } else {
                break;
            }
        }
        (*trocas)++;
        a[j + 1] = x;
        if (j + 1 != i) {
        }
    }
}

int main() {
    int q;
    int *n = NULL;

    scanf("%d", &q);
    n = (int *)malloc(q * sizeof(int));

    for (int i = 0; i < q; i++) {
        scanf("%d", &n[i]);
    }

    int **vetores = (int **)malloc(q * sizeof(int *));
    int **vetoresb = (int **)malloc(q * sizeof(int *));

    for (int i = 0; i < q; i++) {
        vetores[i] = (int *)malloc(n[i] * sizeof(int));
        vetoresb[i] = (int *)malloc(n[i] * sizeof(int));
    }

    for (int i = 0; i < q; i++) {
        for (int j = 0; j < n[i]; j++) {
            scanf("%d", &vetores[i][j]);
        }
    }

    for (int i = 0; i < q; i++) {
        int trocas_insert = 0;
        int comp_insert = 0;

        insert(vetores[i], n[i], &trocas_insert, &comp_insert);
        printf("I %d %d %d\n", n[i], trocas_insert, comp_insert);
        
        int trocas_merge = 0;
        int comp_merge = 0;

        merge(vetores[i], 0, n[i] - 1, vetoresb[i], &trocas_merge, &comp_merge);
        printf("M %d %d %d\n", n[i], trocas_merge, comp_merge);
    }

    for (int i = 0; i < q; i++) {
        free(vetores[i]);
        free(vetoresb[i]);
    }
    free(vetores);
    free(vetoresb);
    free(n);

    return 0;
}

Answer 1

您首先要就地进行插入排序。然后对排序后的数组进行合并排序。如果注释掉插入排序，您就会得到合并排序的正确答案。

如果我使用第三个数组作为输入，并在每次排序之前将其复制到

vetores

，则会输出正确的答案。