这个题目容易写出个一个不易察觉的BUG
数据如下:
4
1 2 4 3
1 2 4 3
如果你输出如下,就是对的, 否则就是错的!!
Insertion Sort
1 2 3 4
/*
* Author: Apprentice_lb
* Created Time: 2022/2/20 13:35:22
* File Name: pat.cpp
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
const int N = 200 + 10;
int a[N], b[N], c[N];
int n;
void down(int n, int d){
if(2 * d >= n) return;
int tmp;
if(2 * d + 1 >= n) tmp = b[d * 2];
else if(2 * d + 1 < n) tmp = max(b[d * 2], b[d * 2 + 1]);
if(tmp < b[d]) return;
else if(2 * d + 1 < n && b[d*2+1] > b[d*2]){
swap(b[2 * d + 1], b[d]);
down(n, 2 * d + 1);
}else{
swap(b[2 * d], b[d]);
down(n, 2 * d);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= n; i++) cin >> b[i];
int sign = 0;
for(int i = 1; i < n; i++){
sort(c + 1, c + i + 1);
if(memcmp(b, c, sizeof c) == 0){
sign = i;
break;
}
}
if(sign){
cout << "Insertion Sort\n";
int j;
for(j = 2; j < n; j++)
if(b[j] < b[j - 1]) break;
sort(c + 1, c + j + 1);
for(int i = 1; i <= n; i++){
if(i == 1) cout << c[i];
else cout << " " << c[i];
}
}else{
cout << "Heap Sort\n";
sort(c + 1, c + n + 1);
int j;
for(j = n; j > 1; j--){
if(c[j] != b[j]) break;
}
swap(b[1], b[j]);
down(j, 1);
for(int i = 1; i <= n; i++){
if(i == 1) cout << b[i];
else cout << " " << b[i];
}
}
cout << '\n';
return 0;
}