1098 insertion or heap sort (25 points)

Answer key

Now the brain is slow , After reading Liu Shen's explanation , Her explanation is really beautiful
work through Don't feel superfluous code And it's very readable
Blog here , For personal notes only
And I feel that blogging helps clear your mind

Answer key
Two situations are required ：

1. Insertion sort ： The first few elements are sequential , The last few elements are in the same order as the initial sequence
2. Heap sort ： The last few elements are sequential , The first few elements are a big top heap

solve ：

1. Insertion sort ： Find two parts （ Sequence and are not sequence ） The dividing point of For the number of the first few elements +1 The number of March on sort
2. Heap sort ： Find the dividing point , It's easy to see ,b[1] Is the maximum value of the large top stack , It must be the minimum value of the ordered elements
   so , From the back to the front

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int n = 110;
int a[n], b[n];
int N;

int get_index()
{
    
    int i = 1;
    while (i <= N && b[i - 1] <= b[i])
        i++;
    int index = i;
    while (i <= N && a[i] == b[i])
        i++;
    return (i == N + 1 ? index : 0);
}
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 index = get_index();

    if (index)
    {
    
        cout << "Insertion Sort\n";
        sort(b + 1, b + index + 1);
    }
    else
    {
    
        cout << "Heap Sort\n";
        index = N;
        while (index >= 2 && b[index] >= b[1])
            index--;
        swap(b[index], b[1]);
        //  Build heap functions 
        //  The first few   Just make a heap 
        make_heap(b + 1, b + index);
    }
    for (int i = 1; i <= N; i++)
    {
    
        if (i != 1)
            cout << " ";
        cout << b[i];
    }

    return 0;
}