第四章排序 AcWing 1579. 插入还是归并

妖狐艹你老母 2023-09-24 13:56 55阅读 0赞

## 第四章 排序 AcWing 1579. 插入还是归并 ##

### 原题链接 ###

[AcWing 1579. 插入还是归并][AcWing 1579.]

### 算法标签 ###

排序

### 思路 ###

对于插入排序还是堆排序排序过程要有所了解  
插入排序：基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表  
归并排序：采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 若将两个有序表合并成一个有序表，称为二路归并  
经过一定次数的迭代后， 插入排序与归并排序应具有如下特征  
![在这里插入图片描述][9dbf1c44f4734357996008777010c270.png]  
显然， 插入排序更容易判断（实际上， 也可以判断是否是归并排序）， 判断排序类型后， 对插入排序或归并排序进行模拟， 输出模拟迭代后的序列。  
这里有一个技巧： 对于下一轮迭代后的序列， 可以进行模拟， 但由于已知下一轮排序的起始点， 因此可以使用快排（即sort函数）模拟， 无论是从时间复杂度，空间复杂度，编程难度等方面来看，使用快排（即sort函数）模拟都优于对插入排序或归并排序进行模拟

### 代码 ###

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N = 105;
    //int t, n, m, cnt, ans; 
    int n;
    int a[N], b[N];
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	n=rd();
    	rep(i, 1, n+1){
    	    a[i]=rd();
    	}
    	rep(i, 1, n+1){
    	    b[i]=rd();
    	}
    	
    	int p=0;
    	// 注意 由于数组中可能存在相等值 此处使用<=进行比较 即保持非降序即可
    	while(p+1<=n&&b[p]<=b[p+1]){
    	    p++;
    	}
    	// [0-p] 前半部分有序元素  [p+1-n] 后半部分无序元素
    	int pp=p+1;
    	while(p+1<=n&&b[p+1]==a[p+1]){
    	    p++;
    	}
    	if(p==n){
    	    puts("Insertion Sort");
    	    // 模拟插入排序
    	    while(pp>1&&b[pp]<b[pp-1]){
    	        swap(b[pp], b[pp-1]);
    	        pp--;
    	    }
    	    printf("%lld", b[1]);
    	    rep(i, 2, n+1){
    	        printf(" %lld", b[i]);
    	    }
    	}else{
    	    puts("Merge Sort");   
    	    int k=1;
    	    while(true){
    	        int p=1;
    	        while(b[p]==a[p]){
    	            p++;
    	            if(p==n+1){
    	                break;
    	            }
    	        }
    	        int len=1<<k;
    	        for(int i=1; i<=n; i+=len){
    	        	// 使用快排模拟
    	            sort(a+i, a+min(i+len, n+1));
    	        }
    	        // 注意 外层循环跳出语句须位于快排模拟后， 保证快排模拟后跳出外层循环
    	        if(p==n+1){
    	            break;
    	        }
    	        k++;
    	    }
    	    printf("%lld", a[1]);
    	    rep(i, 2, n+1){
    	        printf(" %lld", a[i]);
    	    }
    	}
    	return 0;
    }

### 参考文献 ###

[AcWing 1579. 插入还是归并（PAT甲级辅导课）][AcWing 1579. _PAT]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1579.]: https://www.acwing.com/problem/content/1581/
[9dbf1c44f4734357996008777010c270.png]: https://img-blog.csdnimg.cn/9dbf1c44f4734357996008777010c270.png
[AcWing 1579. _PAT]: https://www.acwing.com/video/1226/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png