[归并排序]数组法（c++)

解题思路:先分别将两个数组各自排序，再使用归并排序

注意事项:

参考代码:

#include <iostream>

using namespace std;

int main() {

int n, m, t;

cin >> n >> m;

int a[n][2], b[m][2], c[m + n][2];

for (int i = 0; i < n; i++)

for (int j = 0; j < 2; j++)

cin >> a[i][j];

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

for (int j = 0; j < 2; j++)

cin >> b[i][j];

for (int i = 0; i < n - 1; i++)

for (int j = 0; j < n - 1 - i; j++) {

if (a[j][0] > a[j + 1][0]) {

t = a[j][0];

a[j][0] = a[j + 1][0];

a[j + 1][0] = t;

t = a[j][1];

a[j][1] = a[j + 1][1];

a[j + 1][1] = t;

}

}

for (int i = 0; i < m - 1; i++)

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

if (b[j][0] > b[j + 1][0]) {

t = b[j][0];

b[j][0] = b[j + 1][0];

b[j + 1][0] = t;

t = b[j][1];

b[j][1] = b[j + 1][1];

b[j + 1][1] = t;

}

}

int p = 0, q = 0;

for (int i = 0; i < m + n && p < n && q < m; i++) {

if (a[p][0] < b[q][0]) {

c[i][0] = a[p][0];

c[i][1] = a[p][1];

p++;

} else {

c[i][0] = b[q][0];

c[i][1] = b[q][1];

q++;

}

}

if (p == n && q < m) {

for (int i = n + q  ; i < m + n; i++) {

c[i][0] = b[q][0];

c[i][1] = b[q][1];

q++;

}

} else if (p < n && q == m) {

for (int i = m + p ; i < m + n; i++) {

c[i][0] = a[p][0];

c[i][1] = a[p][1];

p++;

}

}

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

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

cout << c[i][j] << " ";

}

cout << endl;

}

return 0;

}