基本归并排序练习

Question

需求：根据下面提供的代码，实现归并排序算法，重新排列一个包含N个元素的数组。运行算法时，每次合并两个子数组后打印数组 A。

输入

• 第一行是一个正整数 N (0 < N < 20)
• 下一行包含N个整数，它们是数组的元素

输出

• 接下来的几行打印出数组 A 的配置。

示例：

输入

10

800 728 703 671 628 625 518 508 392 331

输出

[ 728 800 ] 703 671 628 625 518 508 392 331

[ 703 728 800 ] 671 628 625 518 508 392 331

703 728 800 [ 628 671 ] 625 518 508 392 331

[ 628 671 703 728 800 ] 625 518 508 392 331

628 671 703 728 800 [ 518 625 ] 508 392 331

628 671 703 728 800 [ 508 518 625 ] 392 331

628 671 703 728 800 508 518 625 [ 331 392 ]

628 671 703 728 800 [ 331 392 508 518 625 ]

[ 331 392 508 518 625 628 671 703 728 800 ]

我很难找到一种方法来在每次合并后打印出数组的剩余元素。 这是我的代码，希望任何人都可以帮助我：

#include <iostream>

using namespace std;

void printArray(int arr[], int start, int end) {
    cout << "[ ";
    for (int i = start; i <= end; ++i) {
        cout << arr[i];
        if (i < end) {
            cout << " ";
        }
    }
    cout << " ] ";
}

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            ++i;
        } else {
            arr[k] = R[j];
            ++j;
        }
        ++k;
    }

    while (i < n1) {
        arr[k] = L[i];
        ++i;
        ++k;
    }

    while (j < n2) {
        arr[k] = R[j];
        ++j;
        ++k;
    }

    // In ra mảng sau mỗi lần trộn hai mảng con
    printArray(arr, left, right);
    cout << endl;

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int N;
    cin >> N;

    int* arr = new int[N];
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    mergeSort(arr, 0, N - 1);

    delete[] arr;

    return 0;
}

运行我的代码后，这是示例的输出：

[ 728 800 ]

[ 703 728 800 ]

[ 628 671 ]

[ 628 671 703 728 800 ]

[ 518 625 ]

[ 508 518 625 ]

[ 331 392 ]

[ 331 392 508 518 625 ]

[ 331 392 508 518 625 628 671 703 728 800 ]

如您所见，这不包含整个数组，而仅打印已合并的元素，我希望它看起来像输出示例。

Answer 1

根本问题是

printArray

并不是设计来打印整个数组的。它只知道打印

start

和

end

之间的元素。它不知道打印

start

之前的元素以及

end

之后的元素。

要让

printArray

打印所有元素，您必须向

printArray

传递总共有

N

个元素的信息，而不仅仅是

start

和

end

。一旦完成，那么

printArray

需要做的就是

1. 打印

   start

   之前的元素。
2. 打印

   start

   和

   end

   之间的元素。
3. 打印

   end

   之后的元素。

最简单的方法是向

merge

、

mergeSort

和

printArray

函数添加一个额外参数，表示数组中的元素数量：

1. void merge(int arr[], int left, int mid, int right, int numElements)

2. void mergeSort(int arr[], int left, int right, int numElements)

3. void printArray(int arr[], int start, int end, int numElements)

在

main

中，您可以这样调用

mergeSort

：

mergeSort(arr, 0, N - 1, N);

并且所有对

mergeSort

、

merge

和

printArray

的调用都会传递

numElements

的值，最终以

printArray

结束。

那么

printArray

，功能就很简单了：

void printArray(int arr[], int start, int end, int numElements) {
    
    for (int i = 0; i < start; ++i)
        std::cout << arr[i] << " ";

    cout << "[ ";
    for (int i = start; i <= end; ++i) {
        cout << arr[i];
        if (i < end) {
            cout << " ";
        }
    }
    cout << " ] ";

    for (int i = end + 1; i < numElements; ++i)
        std::cout << arr[i] << " ";
}

现场演示