堆排序：先建堆，每次从堆顶拿出一个元素，放到堆的末尾，然后调整堆的大小（-1），将调整大小后的堆的最后一个元素放到堆顶，然后将该堆顶元素下滤，再次将数组调整为堆。
为了让下滤操作不越界，将数组开得较大，并且初值设为int最小值。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MIN = 0x80000000;
int n;
vector<int> initial(200), partial(200);
bool check(vector<int> v) {
for (int i = 0;i < n;i++) {
if (v[i] != partial[i])
return false;
}
return true;
}
bool isInsertionSort = false;
void insertionSort(vector<int> v) {
for (int i = 1;i < n;i++) {
int temp = v[i],
pos = i; //v[i]插入位置
while (pos > 0 && v[pos - 1] > temp) {
v[pos] = v[pos - 1];
pos--;
}
v[pos] = temp;
if (isInsertionSort == true) {
printf("Insertion Sort\n");
for (int j = 0;j < n;j++) {
if (j != 0)
printf(" ");
printf("%d", v[j]);
}
return;
}
isInsertionSort = check(v);
}
}
void percolateDown(int index, int rear) {
int left = index * 2 + 1, right = index * 2 + 2;
while (left < rear) {
int pos = initial[left] > initial[right] ? left : right;
if (initial[pos] <= initial[index]) {
break;
}
int temp = initial[index];
initial[index] = initial[pos];
initial[pos] = temp;
index = pos;
left = index * 2 + 1, right = index * 2 + 2;
}
}
bool isHeapSort = false;
void heapSort() {
for (int i = n - 1;i >= 0;i--) {
percolateDown(i, n);
}
int rear = n;
while (rear > 0) {
int temp = initial[0];
initial[0] = initial[rear - 1];
percolateDown(0, rear - 1);
initial[rear - 1] = temp;
rear--;
if (isHeapSort) {
printf("Heap Sort\n");
for (int j = 0;j < n;j++) {
if (j != 0)
printf(" ");
printf("%d", initial[j]);
}
return;
}
if (check(initial))
isHeapSort = true;
}
}
int main() {
fill(initial.begin(), initial.end(), MIN);
scanf("%d", &n);
for (int i = 0;i < n;i++) {
scanf("%d", &initial[i]);
}
for (int i = 0;i < n;i++) {
scanf("%d", &partial[i]);
}
insertionSort(initial);
if (!isInsertionSort) {
heapSort();
}
}