[PAT解题报告] Insertion or Heap Sort
和1089差不多……也是判断插入排序，另外一种排序是堆排序。关于插入排序，和1089判断方法相同，不过这次我没有对每个前i项单独排序，而是模拟了插入排序的过程，直到找到和输入相等的时候，再继续到第一个不同的时候。
对于堆排序也是模拟，每次deleteMax,把最大的放入堆的最后，并且把堆的size减小1，这样每次后缀都是排好顺序的，关键是实现堆排序的down函数，就是把某个位置（可能）不符合要求的下移动，维护堆的性质。比1089还是难一些，因为堆排序相对难写。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int a[102], b[102], c[102];
void print(int *a, int n) {
for (int i = 0; i < n; ++i) {
if (i) {
putchar(' ');
}
printf("%d", a[i]);
}
puts("");
}
bool same(int *a,int *b, int n) {
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
void insertion(int *a, int i) {
int temp = a[i];
for (--i; (i >= 0) && (a[i] > temp); --i) {
a[i + 1] = a[i];
}
a[i + 1] = temp;
}
bool make1(int n) {
bool mark = false;
for (int i = 1; i < n; ++i) {
insertion(c, i);
if (same(c, b, n)) {
mark = true;
}
else if (mark) {
puts("Insertion Sort");
print(c, n);
return true;
}
}
return false;
}
void down(int *a, int i, int n) {
for (;;) {
int left = (i << 1) | 1;
if (left >= n) {
break;
}
int right = left + 1;
int x = ((right < n) && (a[right] > a[left]))?right:left;
if (a[i] > a[x]) {
break;
}
swap(a[x], a[i]);
i = x;
}
}
void deleteMax(int *a,int &n) {
swap(a[0], a[--n]);
down(a, 0, n);
}
void make2(int n) {
puts("Heap Sort");
for (int i = (n >> 1) - 1; i >= 0; --i) {
down(a, i, n);
}
int m = n;
while (!same(a, b, n)) {
deleteMax(a, m);
}
while (same(a, b, n)) {
deleteMax(a, m);
}
print(a, n);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
memcpy(c, a, sizeof(int) * n);
for (int i = 0; i < n; ++i) {
scanf("%d", b + i);
}
if (!make1(n)) {
make2(n);
}
return 0;
}
原题链接； http://www.patest.cn/contests/pat-a-practise/1098
