插入排序直接用sort即可，第一次的插入排序是前两个元素（因为插入排序是手里先拿着第一个，后序的往里面插入）
堆排序采用的是最大堆，因为要求的是从小到大的序列，每次都是堆的堆顶最大和n的元素交换
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 110;
int initial[maxn], target[maxn], temp[maxn], n;
bool issame(int a[])
{
for (int i = 1; i <= n; i++)
{
if (a[i] != target[i])return false;
}
return true;
}
bool isinsert(int a[])
{
bool flag = false;
for (int i = 2; i <= n; i++)
{
if (i!=2&&issame(a))flag = true;
//注意sort的范围是+i+1，因为数组序号是1-n，不是0-n
sort(a + 1, a + i + 1);
if (flag)return true;
}
return false;
}
void downAdjust(int low, int high)
{
int i = low, j = 2 * i;
while (j <= high)
{
if (j + 1 <= high&&temp[j + 1] > temp[j])j++;
if (temp[i] < temp[j])
{
swap(temp[i], temp[j]);
i = j;
j = i * 2;
}
else return;
}
}
void showarr(int a[])
{
for (int i = 1; i <= n; i++)
{
printf("%d", a[i]);
if (i != n)printf(" ");
}
}
void Heapsort()
{
for (int i = n / 2; i >= 1; i--)downAdjust(i, n);
bool flag = false;
for (int i = n; i>1;i--)
{
if (i!=n&&issame(temp))flag = true;
swap(temp[1], temp[i]);
downAdjust(1, i-1);
if (flag == true)break;
}
showarr(temp);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &initial[i]), temp[i] = initial[i];
for (int i = 1; i <= n; i++)scanf("%d", &target[i]);
if (isinsert(initial))
{
printf("Insertion Sort\n");
showarr(initial);
}
else
{
printf("Heap Sort\n");
Heapsort();
}
return 0;
}
