开发者社区人工智能文章正文

1098. Insertion or Heap Sort (25) 21'

2018-03-06 1119

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： #include #include #include using namespace std;vector a, b;//note:堆排序从1开始void downAdjust(int low, int high...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
//note:堆排序从1开始
void downAdjust(int low, int high){
    int i = 1, j = i * 2;
    while (j <= high) {
        if(j + 1 <= high && b[j] < b[j] + 1)
            j = j + 1;
        if (b[i] < b[j]) {
            swap(b[i], b[j]);
            i = j;
            j = i * 2;
        }else break;
    }
}

int main(){
    int n;
    cin >> n;
    a.resize(n+1);
    b.resize(n+1);
    for (int i = 1; i <= n; i++)  cin >> a[i];
    for (int i = 1; i <= n; i++)  cin >> b[i];
    int i, j;
    for (i = 1; i <= n - 1 && b[i] <= b[i+1]; i++);
    for (j = i + 1; a[j] == b[j] && j <= n; j++) ;
    if (j == n+1) {
        cout << "Insertion Sort" << endl;
        sort(b.begin() + 1, b.begin() + i + 2);
    }else{
        cout << "Heap Sort" << endl;
        j = n;
        while(j >= 2 && b[j] >= b[j - 1]) j--;
        swap(b[1], b[j]);
        downAdjust(1, j - 1);
    }
    for (int i = 1; i <= n; i++)
        printf("%d%c", b[i], i == n ? '\n' : ' ');
    return 0;
}