原题链接
分析：每次排序 每次判断 记录下标 再次排序 按格式输出 插入排序：直接用sort i记录的是每次拍好序的末位置。 堆排序： 就不用再创建堆写堆排序什么的了 serve提供的序列就是可以直接应用的堆 堆本应堆顶最大，从后往前找到第一个小于当前堆顶的下标p，与堆顶数据进行交换，向下调整serve[1] - serve[p-1].
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 110; int n; //序列中有多少个元素 int cop[maxn],origin[maxn], serve[maxn];//原始序列 提供的序列 bool issame(int A[], int B[]) //判断AB是否相等 { for(int i = 1; i <= n; i++) { if(A[i] != B[i]) return false; } return true; } void output(int A[]) { for(int i = 1; i <= n; i++) { cout<< A[i]; if(i < n) cout << " "; else cout << endl; } } void adjustdown(int (&origin)[maxn],int low, int high) { //low为需要调整的下标 int i = low; int j = i * 2; while(j <= high) { if( j+1 <= high && origin[j+1] >origin[j]) { j = j+1; } if( origin[i] < origin[j]) { swap(origin[j], origin[i]); i = j; j = i * 2; } else break; } } int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> origin[i]; } for(int i = 1; i <= n; i++) { cin >> serve[i]; } //插入排序 int k;//记录已排好序的末位置 bool flag = false; for(int i = 2; i <= n; i++)//排序n-1趟 { sort(origin + 1, origin + i + 1); if(!flag && issame(origin, serve)) { flag = true; k = i; break; } } if(flag) { cout << "Insertion Sort" << endl; sort(origin + 1,origin + k + 2); output(origin); } else { cout << "Heap Sort" << endl; int p = n; while(p > 2 && serve[p] >= serve[1]) p--; swap(serve[p],serve[1]); adjustdown(serve, 1, p-1); output(serve); } return 0; }