问题标题: 酷町堂：开学前的小王课堂~~~

上节课我们讲到了排序中的一种：选择排序

选择排序需要双重循环，时间复杂度很高，算是一种比较缓慢的排序，今天我们要讲的是很快的一种排序方式：归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之

归并排序时间复杂度只有O(n log n)，很快的一种算法，跟快排的系统时间复杂度是一样的，但快排和堆排序都不是很稳定：

/*

归并排序是稳定的
快速排序和堆排序都不稳定
不稳定：就是大小相同的两个数，经过排序后，最终位置与初始位置交换了。
快速排序：
27 23 27 3
以第一个27作为pivot中心点，则27与后面那个3交换，形成
3 23 27 27，排序经过一次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。
堆排序：
比如：3 27 36 27，
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。”
2 归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。

(摘自百度~)

*/

所以学习归并排序是一个很好的排序方法，但是代码实现比较长，况且C++没有帮你弄好直接用的函数，所以要自己模拟规则排序

下面讲解酷町堂网站4518 合并有序数组题目

思路：

1、将两个已经有序数组合并成一个，拿两个数组的第一个数字进行比较，小的数字放入新数组，一直重复
2、直到有一个数组为空，将另一个数组剩下的数字接到后面。

代码实现(模板)：

#include <iostream>
using namespace std;
int a[1005], b[1005], c[2005], m, n; 
int main() {
    cin >> m >> n;
    for(int i=1; i<=m; i++) {
        cin >> a[i];
    } 
    for(int i=1; i<=n; i++) {
        cin >> b[i];
    } 
    int i = 1, j = 1, k = 0;
    while(i<=m && j<=n) {
        if(a[i] < b[j]) {
            c[++k] = a[i];
            i ++;
        }else {
            c[++k] = b[j];
            j ++;
        }
    }
    while(i<=m) {
        c[++k] = a[i];
        i ++;
    }
    while(j<=n) {
        c[++k] = b[j];
        j ++;
    }
    for(int i=1; i<=k; i++) {
        cout << c[i] << ' ';
    }
    return 0;
}
//一定要看懂再复制，不然会被处罚的！~

代码很长，需要一步一步归纳。

今天作业：

一道难题1445 瑞士轮，很难很难，做出来要发截图，不允许更改审查元素，需要发两张图片，一张是提交记录，一张是提交结果的全张图片，因为题目很难，此题有50个豆子！！如果一个礼拜后没有正解加至100豆！！！

此作业提交记录在春季或者冬季的不算数，因为是老师带着写的！！！

王子健在2020-08-27 20:47:54追加了内容

@陈曦    是这样的提交结果：