在C++中合并排序实现

Question

我正在学习如何在c ++中实现mergesort并遇到以下问题.

这是我的合并函数,它将两个已排序的数组合并为一个已排序的数组.

void merge(int *list, int *final, int start, int mid, int stop) {
    int h = start;
    int i = start;
    int j = mid + 1;

    while ((h <= mid) && (j <= stop)) {
        if (list[h] <= list[j]) {
            final[i] = list[h];
            h++;
        } else {
            final[i] = list[j];
            j++;
        }
        i++;
    }

    /* CODE A */
    if (h > mid) {
        for (int k = j; k <= stop; k++) {
            final[i] = list[k];
            i++;
        }
    } else {
        for (int k = h; k <= mid; k++) {
            final[i] = list[k];
            i++;
        }
    }
    /* End of CODE A */

    /* CODE B */
    while ( h <= mid) {
        list[i] = final[h];
        i++; h++;
    }

    while ( j <= stop ) {
        list[i] = final[j];
        i++; j++;
    }
    /* End of CODE B */

    for (int k = start; k <= stop; k++) {
        list[k] = final[k];
        printArray(list, 4, "Intermediate Array: ");
    }
}

在任何时候,我都使用CODE A或CODE B.当我使用CODE A时,该函数按预期执行.但是,当我使用CODE B时,该函数用随机数据填充数组列表.

printArray是一个打印数组列表的自定义函数.排序一组数字{4,2,6,9}时,我从printArray函数得到这个输出:

Intermediate Array: 2 2 6 9 <br>
Intermediate Array: 2 -790123182 6 9<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>

Answer 1

在代码B中,来自listto 的赋值final方向错误.试试这个:

/* CODE B */
while ( h <= mid) {
    final[i] = list[h];
    i++; h++;
}

while ( j <= stop ) {
    final[i] = list[j];
    i++; j++;
}
/* End of CODE B */