第四章排序8 AcWing 1588. 插入还是堆排序

我不是女神ヾ 2023-09-24 13:56 26阅读 0赞

## 第四章 排序8 AcWing 1588. 插入还是堆排序 ##

### 原题链接 ###

[AcWing 1588. 插入还是堆排序][AcWing 1588.]

### 思路 ###

对于插入排序还是堆排序排序过程要有所了解  
插入排序：基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表  
堆排序：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点  
经过一定次数的迭代后， 插入排序与堆排序应具有如下特征  
![在这里插入图片描述][18a02aba53c147b4852ff4de0c034a3c.png]  
显然， 插入排序更容易判断（实际上， 也可以判断是否是堆排序， 但是堆排序需要将前面数组构造为堆， 相对麻烦）， 判断排序类型后， 对插入排序或堆排序进行模拟， 输出模拟迭代后的序列。

### 代码 ###

#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 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);
    }
    // 堆排序
    // 1.swap(堆顶,堆底);
    // 2.左大=左，右大=右，交换，继续down
    void down(int u, int n){
        int t=u;
        if(u*2<=n&&b[t]<b[u*2]){
            t=u*2;
        }
        if(u*2+1<=n&&b[t]<b[u*2+1]){
            t=u*2+1;
        }
        if(t!=u){
            swap(b[t], b[u]);
            down(t, n);
        }
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int 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--;
    	    }
    	}else{
    	    puts("Heap Sort");   
    	    pp=n;
    	    // 寻找堆尾元素
    	    while(b[pp]>=b[1]){
    	        pp--;
    	    }
    	    // 交换堆尾元素与堆顶元素
    	    swap(b[1], b[pp]);
    	    // 模拟堆排序
    	    down(1, pp-1);
    	}
    	printf("%lld", b[1]);
    	rep(i, 2, n+1){
    	    printf(" %lld", b[i]);
    	}
    	return 0;
    }

### 参考文献 ###

[AcWing 1588. 插入还是堆排序（PAT甲级辅导课）][AcWing 1588. _PAT]

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

[AcWing 1588.]: https://www.acwing.com/problem/content/1590/
[18a02aba53c147b4852ff4de0c034a3c.png]: https://img-blog.csdnimg.cn/18a02aba53c147b4852ff4de0c034a3c.png
[AcWing 1588. _PAT]: https://www.acwing.com/video/1024/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png