（坚持每天都写算法）算法基础复习part1基础算法1-2—

前言：本来想着找模板，但是第一篇的观感我自己觉得还可以（摆烂），所以就不搞了。

归并排序，是一种分治算法。当问题具有最优子结构并且子问题之间是互相独立的再加上子问题的规模可以是很小以至于很容易解决的以及子问题可以合并成整个问题的解，那么就可以考虑使用分治算法。子问题互相独立，即各个子问题所占的资源是独立的。举个例子，棋盘问题就是典型的分治算法，做法是先将棋盘分成几个小棋盘，而几个小棋盘就是互相独立的。

分治算法的解题步骤是先分割子问题，每一个子问题的步骤，合并成整个问题的解。

归并排序是先将数组分成无数个独立的小数组，每两个小组进行比较，由于每个小组都是独立的，可能会出现1 8 ， 2 3 ，这种情况，为了正确排序，就需要两个指针i和j，排序顺序应该是1<2，排完序的数组k ：1 ，8 <2 , 数组k：1 8，8 < 3，数组k：1 2 3，最后只剩下8，最后放进去，数组k：1 2 3 8。这里2和3一定是顺序的因为在这个例子之前已经排过了。然后数组k就会变成上一个栈的一个数组，就类似于这里的1 8 ，每个子问题做法都是一样，直到得出了最后的答案。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];
int n;
int temp[N];
//建议配上动画和自己模拟一个简单数列来看，大致就可以理清代码逻辑了
//递归左右排序，左右合并排序

void merge_sort(int l , int r , int a[]){
    if(l >= r)return;//注意，只有一个数的话不用排序
    int mid = (l + r)>> 1;//>>的优先级高于+，优先级和执行顺序不一样，优先级可以理解成
    //就是加了个括号
    
    merge_sort(l , mid , a) , merge_sort(mid + 1 , r , a);
    
    int i = l , j = mid + 1 ; //mid加1是为了配合最小的序列只有两个数，因为i还是有可能等于mid(在只有两个数的时候)
    int k = 0;
    while(i <= mid && j <= r){//i可以等于mid，在数组只有两个数的时候，同理，j可以等于r，j= mid + 1
        if(a[i] <= a[j]) temp[k ++] = a[i ++];//i和j顺便移个位置
        else temp[k ++] = a[j ++];
        //第一个条件为什么要与，因为我们这里要排好序，淘汰掉一个i或者j，剩下来的那个肯定在排好序的子数组里，直接输出即可，也就是
        //下面的操作
    }
    while(i <= mid) temp[k ++] = a[i ++];//淘汰掉一个后输出排好序的子数组
    while(j <= r) temp[k ++] = a[j ++];
    
    for(i = l , j = 0 ; i <= r ; i ++ , j ++) a[i] = temp[j];//最不容易记住的一个，每一次都要将替代数组传给a，i不一定等于0，但是j要设置为0
}

int main(){
    cin >> n;
    //这里和快排一样，也是边界为0
    for(int i = 0 ; i < n ; i ++){
        cin >> a[i];
    }
    merge_sort(0,n-1,a);
    
    for(int i = 0 ; i < n ; i ++){
        printf("%d " , a[i]);
    }
    return 0;
}