问题 B: 基础排序III：归并排序



#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

void merge(int a[], int l1, int r1, int l2, int r2) {

    int i = l1, j = l2;

    int n = r2 - l1 +1;

    int temp[n];

    int index = 0;

    while (i <= r1 && j <= r2) {

        if (a[i] == a[j]) {

            temp[index++] = a[i++];

        } else if (a[i] < a[j]) {

            temp[index++] = a[i++];

        } else {

            temp[index++] = a[j++];

        }

    }

    while (i <= r1) temp[index++] = a[i++];

    while (j <= r2) temp[index++] = a[j++];

    for (int i1 = 0; i1 < n; ++i1) {

        a[l1 + i1] = temp[i1];

    }

}

void merge_sort(int a[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        merge_sort(a, left, mid);

        merge_sort(a, mid + 1, right);

        merge(a, left, mid, mid + 1, right);

    }

}

int main() {

    int n;

    while (scanf(" %d", &n) != EOF) {

        for (int k = 0; k < n; ++k) {

            int m;

            scanf("%d",&m);

            int a[m];

            for (int i = 0; i < m; ++i) {

                scanf("%d", &a[i]);

            }

            merge_sort(a, 0, m - 1);

            for (int j = 0; j < m; ++j) {

                printf("%d\n", a[j]);

            }

        }

    }

    return 0;

}
巴特西

问题 B: 基础排序III：归并排序

最新文章

热门文章
