слияние двух отсортированных массивов

Question

void fus(int *A, int *B, int *C, int n, int m) {
    int j, k, d = n + m;
    for (i = 0, j = 0, k = 0; j < m && i < n && k < d; i++, j++, k++) {
        if ((*(A+i)) < (*(B+j))) {
            (*(C+k)) = (*(A+i));
        } else
            (*(C+k)) = (*(B+j));
    }
}

У меня есть возможность поместить все эти условия в for?

Я не знаю, почему это не работает, и я хотел получить отсортированный массив

Answer 1

i и j не нужно увеличивать на каждой итерации.Увеличьте i, если A [i] Создайте цикл, продолжающийся до тех пор, пока i<n и j<m:

for(i=0, j=0, k=0; j<m && i<n; k++)
{
    if ( A[i] < B[j] )
       C[k] = A[i++];
    else
       C[k] = B[j++];
}      

В концеэтот цикл либо i == n, либо j == m, но он не может быть заполнен обоими одновременно.
Поэтому вам необходимо скопировать недостающий остаток в контейнер:

for(; i<n; i++, k++)
    C[k] = A[i];
for(; j<m; j++, k++)
    C[k] = B[j];

Полный код может выглядеть следующим образомэто:

void fus(int *A, int *B, int *C, int n, int m)
{
    int i=0, j=0, k=0;

    for(; j<m && i<n; k++)
        C[k] = A[i] < B[j] ? A[i++] : B[j++];

    for(; i<n; i++, k++)
        C[k] = A[i];
    for(; j<m; j++, k++)
        C[k] = B[j];
}

Конечно, это может быть даже выражено короче:

void fus(int *A, int *B, int *C, int n, int m)
{
    int i=0, j=0, k=0;  
    while (i<n || j<m)
        C[k++] = i!=n && (j==m || A[i] < B[j]) ? A[i++] : B[j++];
}

Answer 2

Вы должны увеличивать i или j только в зависимости от того, какой элемент вы берете.Кроме того, нет необходимости тестировать k против d, этот тест является избыточным с тестами на i и j.

Также обратите внимание, что слияние не завершено, если вы не закончили копированиеостальные элементы из A или B при i == n или j == m.

Вот исправленная и улучшенная версия с меньшим количеством тестов, использующая синтаксис индекса массива:

void fus(const int *A, const int *B, int *C, int n, int m) {
    int i = 0, j = 0, k = 0;
    if (i < n && j < m) {
        for (;;) {
            if (A[i] <= B[j]) {
                C[k++] = A[i++];
                if (i == n)
                    break;
            } else {
                C[k++] = B[j++];
                if (j == m)
                    break;
            }
        }
    }
    while (i < n)
        C[k++] = A[i++];
    while (j < m)
        C[k++] = B[j++];
}

Answer 3

Rabbid76 обнаружил проблему.

Это проще / понятнее сделать (например) A[i], чем *(A + i)

Кроме того, если A и B имеют разную длину[которые могут быть в операции слияния слиянием слиянием], нам нужны два дополнительных цикла, чтобы скопировать остаток от более длинного из A или B

Кроме того, лучше использовать более описательные имена, чем i, j и т. Д.

Вот исправленная версия [прошу прощения за бесполезную очистку стиля]:

void
fus(int *A, int *B, int *C, int nA, int nB)
{
    int iC = 0;
    int iA = 0;
    int iB = 0;

    for (;  (iA < nA) && (iB < nB);  ++iC) {
        if (A[iA] <= B[iB])
            C[iC] = A[iA++];
        else
            C[iC] = B[iB++];
    }

    for (;  iA < nA;  ++iA, ++iC)
        C[iC] = A[iA];

    for (;  iB < nB;  ++iB, ++iC)
        C[iC] = B[iB];
}