归并排序（c++代码）_归并排序c++代码

原题链接AcWing 787. 归并排序
先看动态示意图
归并排序运用了分治的思想和双指针的算法
将整个区间分为两部分，将数值小的排在前面，数值大的排在后面
最后所有小的都在前面，大的都在后面，达到了排序的目的
总共分为四步
第一步 ：确定递归终止条件
第二步：找到子区间分界点
第三步: 递归排序
第四步：合并子区间
这四步往往第四步是难点也是重点

具体逻辑请看代码以及注释，注释写的比较清晰了

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

using namespace std;

const int N=1001001;
int n;//n个数字
int arr[N];//总数组
int t[N];//临时数组

void Mysort(int l,int r){

    // 1 第一步 退出递归的边界条件
    if(l>=r)return ;//当只有0个或者1个数字时，没有排序的必要，退出递归
     
    // 2 第二步 确定区间分界线
    int mid = l+r>>1;
    
    // 3 第三步 递归排序
    Mysort(l,mid);//左区间
    Mysort(mid+1,r);//右区间
    
    // 4 合并区间
    
    int i=l,j=mid+1;  //i和j分别是两个区间的起点
    
    int k=0;//数组的下标索引
    
    while(i<=mid&&j<=r){  //合并区间，小的排在前面
        if(arr[i]<=arr[j])t[k++]=arr[i++];
        else t[k++]=arr[j++];
        
    }

  //将剩余的直接接在数组的后面
   while(i<=mid)t[k++]=arr[i++];
   while(j<=r)t[k++]=arr[j++];
   
   //将临时数组复制给真正的数组
   //l<=i<=r 的原因是只把已经排序了的部分复制给原数组
  for (i = l, j = 0; i <= r; i ++, j ++ ) arr[i] = t[j];
    
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    Mysort(0,n-1);
    for(int i=0 ;i<n;i++){
        cout<<arr[i]<<' ';
    }
    cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57