C++排序算法——合并有序数组

合并有序数组

思路

我们可以设想一个排序的函数
这个函数里
我们有三个while

while(第一次的执行条件)
{先进行第一次的合并
}
while(第二次的合并条件)
{
把a数组在第一次没有排序上的给加进去
}while(第三次的合并条件)
{
把b数组在第一次没有排序上的给加进去
}

看完了这个可爱的(╹▽╹)的伪代码就可以有大概的思路了

就是从两个数组里面选取合适的数字，加入答案数组里面，最后再把剩下我们没有加进去的数字给加进去就可以了
因为第一个while的条件是这样写的：while (i < n && j < m)
所以可以保证在进行第2和3次排序的时候不会混乱

因为已近有一个数组全部插进去了，剩下的数组里的数只会比前面已近插入的数更大！

可爱的代码

因为我可爱的DEV-CPP坏了，所以注释是英文的，请自行销毁

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int a[MAXN], b[MAXN], c[MAXN];
void merge(int a[], int b[], int c[], int n, int m)
{//Sorting beginsint i = 0, j = 0, tot = 0;while(i < n && j < m){if(a[i] < b[j]){c[tot++] = a[i];i++;}else{c[tot++] = b[j];j++;}//Sort a portion of the scores first}while(i < n) c[tot++] = a[i++];while(j < m) c[tot++] = b[j++];for(int k = 0; k < tot; k++) cout << c[k] << ' ';
}
int main()
{int n, m;cin >> n >> m;//Input start!for (int i = 0; i < n; i++) cin >> a[i];//Enter N numbers -> Store in array A (index: a_i)for (int i = 0; i < m; i++) cin >> b[i];//Enter M numbers -> Store in array B (index: b_i)//Input end!//Call sorting functionmerge(a, b, c, n, m);return 0;
}