1098 Insertion or Heap Sort (25 分)

题解

现在脑子比较慢，看了柳神的题解，她的题解真的太好看了
看一遍 感觉不到多余的代码 并且可读性强
在这里写博，仅是个人的笔记使用
并且感觉写博客有助于清晰思路

题解
需要两种情况：

1. 插入排序：前几个元素是顺序的，后几个元素和初始序列的顺序一致
2. 堆排序 ：后几个元素是顺序的，前几个元素是一个大顶堆

解决：

1. 插入排序：找到两个部分（顺序和不是顺序）的分界点 对前几个元素的个数+1 的个数 行进sort
2. 堆排序 ：找到分界点，很容易发现，b[1]是大顶堆的最大值，而一定是已经排过序的元素的最小值
   故，从后先前找即可

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]);
        // 建立堆函数
        // 直接将前几个 做一个堆就行
        make_heap(b + 1, b + index);
    }
    for (int i = 1; i <= N; i++)
    {
    
        if (i != 1)
            cout << " ";
        cout << b[i];
    }

    return 0;
}