和前面的 1088一样的，不过这次是堆排序。
堆排的时候前面是个最大堆，取最大值后调整堆就好。
#include <iostream> #include <algorithm> #define MAX 110 using namespace std; int origin[MAX], half[MAX]; int n; bool IsInserSort() { int p = 2; while (p <= n && half[p-1] <= half[p]) { p++; } int pos = p; while (p <= n && half[p] == origin[p]) { p++; } if (p == n + 1) { sort(origin + 1, origin + pos + 1); return true; } else return false; } void AdjustHeap(int st, int ed) { if (st < ed) { int left = 2 * st; int right = 2 * st + 1; int pos; if (left < ed && right < ed) { if (half[left] > half[right]) pos = left; else pos = right; } else if (left < ed && right >= ed) { pos = left; } else return; if (half[pos] > half[st]) { swap(half[pos], half[st]); AdjustHeap(pos, ed); } else return; } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> origin[i]; } for (int i = 1; i <= n; i++) { cin >> half[i]; } if (IsInserSort()) { cout << "Insertion Sort" << endl; cout << origin[1]; for (int i = 2; i <= n; i++) { cout << " " << origin[i]; } cout << endl; } else { cout << "Heap Sort" << endl; int pre = n; int NowMax[MAX]; int max = -1; for (int i = 1; i <= n; i++) { if (max < half[i]) max = half[i]; NowMax[i] = max; } for (int i = n; i > 0; i--) { if (half[i] < NowMax[i]) {//找到排好和没排好的区分地方 int temp = half[i]; half[i] = half[1]; half[1] = temp; //调整堆 AdjustHeap(1, i); break; } pre = i; } cout << half[1]; for (int i = 2; i <= n; i++) { cout << " " << half[i]; } cout << endl; } return 0; }