题目描述

C++实现

样例

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int a[200];
int b[200];
void down(int u, int n)
{
    int t = u;
    if (u * 2 <= n && b[u * 2] > b[u])
    {
        t = 2 * u;
    }
    if (u * 2 + 1 <= n && b[u * 2 + 1] > b[t])
    {
        t = 2 * u + 1;
    }
    if (u != t)
    {
        swap(b[u], b[t]);
        down(t,n);
    }
}
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= N; i++)
    {
        cin >> b[i];
    }
    int p=1;
    while(p<N&&b[p]<=b[p+1]) p++;
    int index=p+1;
    while(index<=N&&b[index]==a[index]) index++;

    if(index==N+1) {
        cout<<"Insertion Sort"<<endl;
        sort(b+1,b+p+2);//注意是左闭右开
    }
    else
    {
        cout << "Heap Sort" << endl;
        int p = 0;
        for (int i = N-1; i; i--)
        {
            if((b[i]+1)!=b[i+1])
            {
                p=i;
                break;
            }
        }
        down(1, p);
        swap(b[1], b[p]);
        down(1,p-1);
    }
    for (int i = 1; i <= N; i++)
        {
            if(i==N)
            {
                cout << b[i] << "\n";
            }
            else{
                cout << b[i] << " ";
            }
        }
    return 0;
}