1.给出一个初始的排列和一个经过N轮排序的排列，求出是使用插入还是堆排序，并输出下一轮的排列。
2.之前一直开在测试点2里，通过实验知道0、2、4测试点是测插入排序的，1、3、5是堆排的。
3.测试点2卡住，主要是因为插入排序的外层循环我从i=0开始，导致第一步出来的结果和原来的一模一样（i=0，相当于没有进行调整），而把i改为1后，则可以正常AC题目。
4.目前只知道测试点2的情况是，经过若干轮插入排序后，得到的target数组与源数组是一样的，其他细节就无从得知。
5.堆排可以自己写函数，也可以使用make_heap；
6.自己写的堆排的程序：
[c language=”++”]
#define LeftChild(i) (2*(i)+1)
void PercDown(vector<int>&num, int i, int n)
{
int child;
int tmp;
for (tmp = num[i]; LeftChild(i) < n; i = child) { child = LeftChild(i); if (child != n – 1 && num[child + 1] > num[child])
child++;
if (tmp < num[child]) num[i] = num[child]; else break; } num[i] = tmp; } for (int i = n – 1; i>0; i–)
{//进行堆排
swap(numCopy[0], numCopy[i]);
PercDown(numCopy, 0, i);
}
[/c]
According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1:
10 3 1 2 8 7 5 9 4 6 0 1 2 3 7 8 5 9 4 6 0
Sample Output 1:
Insertion Sort 1 2 3 5 7 8 9 4 6 0
Sample Input 2:
10 3 1 2 8 7 5 9 4 6 0 6 4 5 1 0 3 2 7 8 9
Sample Output 2:
Heap Sort 5 4 3 1 0 2 6 7 8 9
AC代码，使用make_heap：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
10
6 4 5 1 0 3 2 7 8 9
5 4 2 1 0 3 6 7 8 9
*/
int main(void)
{
int n;
cin >> n;
vector<int> num(n, 0);
vector<int> num2(n, 0);
vector<int> numCopy(n, 0);
vector<int> target(n, 0);
for (int i = 0; i < n; i++)
{
scanf("%d", &num[i]);
}
numCopy = num;
num2 = num;
for (int i = 0; i < n; i++)
{
scanf("%d", &target[i]);
}
bool isInsert = false;
for (int i = 1; i < n; i++)
{//进行插入排序,从i=1，即第二个元素开始插入排序，i=0时，没必要进行插入排序（为什么测试点2会错？）
int tmp = num[i];
int j = i;
for (; j>0 && num[j – 1]>tmp; j–)
{
num[j] = num[j – 1];
}
num[j] = tmp;
if (!isInsert && num == target)
{//是插入排序
isInsert = true;
}
else if (isInsert)
{
break;
}
}
if (isInsert)
{
cout << "Insertion Sort" << endl;
for (int i = 0; i < n; i++)
{
cout << num[i];
if (i != n – 1)
cout << " ";
}
cout << endl;
return 0;
}
bool isHeap = false;
for (int i = n-1; i>=0; i–)
{//进行堆排，使用原来的函数进行堆排
make_heap(numCopy.begin(), numCopy.begin() + i+1);
if (!isHeap && numCopy == target)
{
isHeap = true;
}
else if (isHeap)
break;
swap(numCopy[0], numCopy[i]);//注意是比较了后再交换
}
if (isHeap)
{//如果是堆排，输出并return
cout << "Heap Sort" << endl;
for (int i = 0; i < n; i++)
{
cout << numCopy[i];
if (i != n – 1)
cout << " ";
}
cout << endl;
return 0;
}
return 0;
}
[/c]
AC代码，使用自己写的堆排：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
10
6 4 5 1 0 3 2 7 8 9
5 4 2 1 0 3 6 7 8 9
*/
#define LeftChild(i) (2*(i)+1)
void PercDown(vector<int>&num, int i, int n)
{
int child;
int tmp;
for (tmp = num[i]; LeftChild(i) < n; i = child)
{
child = LeftChild(i);
if (child != n – 1 && num[child + 1] > num[child])
child++;
if (tmp < num[child])
num[i] = num[child];
else
break;
}
num[i] = tmp;
}
int main(void)
{
int n;
cin >> n;
vector<int> num(n, 0);
vector<int> num2(n, 0);
vector<int> numCopy(n, 0);
vector<int> target(n, 0);
for (int i = 0; i < n; i++)
{
scanf("%d", &num[i]);
}
numCopy = num;
num2 = num;
for (int i = 0; i < n; i++)
{
scanf("%d", &target[i]);
}
bool isInsert = false;
for (int i = 1; i < n; i++)
{//进行插入排序,从i=1，即第二个元素开始插入排序，i=0时，没必要进行插入排序（为什么测试点2会错？）
int tmp = num[i];
int j = i;
for (; j>0 && num[j – 1]>tmp; j–)
{
num[j] = num[j – 1];
}
num[j] = tmp;
if (!isInsert && num == target)
{//是插入排序
isInsert = true;
}
else if (isInsert)
{
break;
}
}
if (isInsert)
{
cout << "Insertion Sort" << endl;
for (int i = 0; i < n; i++)
{
cout << num[i];
if (i != n – 1)
cout << " ";
}
cout << endl;
return 0;
}
bool isHeap = false;
for (int i = n / 2; i >= 0; i–)
PercDown(numCopy, i, n);
for (int i = n – 1; i>0; i–)
{//进行堆排
swap(numCopy[0], numCopy[i]);
PercDown(numCopy, 0, i);
if (!isHeap && numCopy == target)
{
isHeap = true;
}
else if (isHeap)
break;
//cout << "Heap Sort" << endl;
//for (int i = 0; i < n; i++)
//{
// cout << numCopy[i];
// if (i != n – 1)
// cout << " ";
//}
}
if (isHeap)
{//如果是堆排，输出并return
cout << "Heap Sort" << endl;
for (int i = 0; i < n; i++)
{
cout << numCopy[i];
if (i != n – 1)
cout << " ";
}
cout << endl;
return 0;
}
return 0;
}
[/c]