[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