[编程笔记]-Merge_Sort归并排序

原理

利用分治思想，把数组对半分成两份，各自排好序，再将两个排好序的数组合并成一个数组即可。

（或许有点废话？Σ(っ °Д °;)っ）

实现

这里着重讲以下合并数组的过程：

1. 建立两个指针，指向两边各排好序的数组的首个元素。

2. 对指针指向的元素进行对比，更小的（从小到大排序）插入临时数组，直到其中一个指针走到结尾。

3. 把两个数组中剩下的元素插入临时数组（其实只会有一个有余，这里不做解释）

4. 用临时数组替换原数组中对应元素段。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n;
int a[N],t[N];

void ms(int l,int r){
    if(l>=r)return;
    int m=l+r>>1;
    ms(l,m);ms(m+1,r);
    int k=0,i=l,j=m+1;
    while(i<=m&&j<=r){
        if(a[i]<=a[j])t[k++]=a[i++];
	else t[k++]=a[j++];
    }
    while(i<=m)t[k++]=a[i++];
    while(j<=r)t[k++]=a[j++];
    for(int i=l,j=0;i<=r;i++,j++)a[i]=t[j];
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    ms(0,n-1);
    for(int i=0;i<n;i++)printf("%d ",a[i]);
    return 0;
}

完结撒花o(￣︶￣)o