[PAT解题报告] Insertion or Heap Sort

#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;
}