题目
shrink v. （使）缩小extracting v. 提取rather than 而不是
解决
思路
origin[N]是原始序列, target[N]是目标序列tempOri[N]是原始序列的拷贝，用于过程中一步步排序首先判断是不是插入排序，每一步排序都要比较一次当前序列和目标序列是不是相同，如果相同再排序一步。如果不是，就是堆排序，然后堆排序排序到当前状态，再多排序一步。
实现
Code1
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
int origin[N], target[N], tempOri[N];
int n;
bool isSame(int a[], int b[]){
for(int i=1; i<=n; i++){
if(a[i] != b[i]) return false;
}
return true;
}
bool insertSort(){
bool flag = false;
for(int i=2; i<=n; i++){
if(i != 2 && isSame(tempOri, target)){
flag = true;
}
sort(tempOri, tempOri+i+1);
if(flag == true) return true;
}
return false;
}
void downAdjust(int low, int high){
int i = low;
int j = i*2;
while(j <= high){
if(j+1 <= high && tempOri[j+1] > tempOri[j]){
j = j+1;
}
if(tempOri[j] > tempOri[i]){
swap(tempOri[i], tempOri[j]);
i = j;
j = i * 2;
}else{
break;
}
}
}
void heapSort(){
bool flag = false;
for(int i=n/2; i>=1; i--){
downAdjust(i, n);
}
for(int i=n; i>1; i--){
if(i != n && isSame(tempOri, target)){
flag = true;
}
swap(tempOri[i], tempOri[1]);
downAdjust(1, i-1);
if(flag == true) return;
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &origin[i]);
tempOri[i] = origin[i];
}
for(int i=1; i<=n; i++){
scanf("%d", &target[i]);
}
if(insertSort()){
printf("Insertion Sort\n");
for(int i=1; i<=n; i++){
printf("%d", tempOri[i]);
if(i < n) printf(" ");
}
}else{
printf("Heap Sort\n");
for(int i=1; i<=n; i++){
tempOri[i] = origin[i];
}
heapSort();
for(int i=1; i<=n; i++){
printf("%d", tempOri[i]);
if(i < n) printf(" ");
}
}
return 0;
}
