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 NN (\le 100≤100). Then in the next line, NN integers are given as the initial sequence. The last line contains the partially sorted sequence of the NN 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
自己寫的代碼在下面，但是判的隻有13分，各位網友們能告我哪裡有bug嗎？
#include <iostream>
using namespace std;
bool Check(int a[],int b[],int N)
{
bool flag = true;
for ( int i = 0 ; i < N ; i++){
if ( a[i] != b[i]){
flag = false;
break;
}
}
return flag;
}
void Print(int a[],int N)
{
cout<<a[0];
for (int i = 1 ; i < N ; i++){
cout<<" "<<a[i];
}
}
bool Insert_Sort(int a[],int b[],int N)
{
bool isInsert = false;
for ( int i = 1 ; i < N ; i++){
int tmp = a[i];
int j;
for (j = i ; j > 0 && a[j-1] > tmp ; j--){
a[j] = a[j-1];
}
a[j] = tmp;
if (isInsert){
cout<<"Insertion Sort"<<endl;
Print(a,N);
break;
}else if(Check(a,b,N)){
isInsert = true;
}
}
return isInsert;
}
void PreDown(int a[],int p,int N)
{
int parent,child;
int x = a[p];
for ( parent = p ; (parent * 2 + 1) < N ; parent = child){
child = parent * 2 + 1;
if ( (child != N -1) && ( a[child] < a[child+1])){
child++;
}
if ( x >= a[child]){
break;
}else{
a[parent] = a[child];
}
}
a[parent] = x;
}
void swap(int* a ,int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
bool Heap_Sort(int a[],int b[],int N)
{
bool isHeap = false;
for ( int i = N/2-1 ; i >= 0 ; i--){
PreDown(a,i,N);
}
for ( int i = N-1 ; i > 0 ; i--){
swap(&a[0],&a[i]);
PreDown(a,0,i);
if (isHeap){
cout<<"Heap Sort"<<endl;
Print(a,N);
break;
}else if(Check(a,b,N)){
isHeap = true;
}
}
}
int main()
{
int len;
cin>>len;
int *A,*B,*C;
A = new int[len];
B = new int[len];
C = new int[len];
for ( int i = 0 ; i < len ; i++){
cin>>A[i];
C[i] = A[i];
}
for ( int i = 0 ; i < len ; i++){
cin>>B[i];
}
bool isHeap = Heap_Sort(A,B,len);
if ( isHeap){
return 0;
}else{
bool isInsert = Insert_Sort(C,B,len);
return 0;
}
return 0;
} 複制
下面是網上的AC代碼:
#include <iostream>
#include <algorithm>
using namespace std;
bool isHeapSort(int *init, int *arr, int n);
int getNextHeapSortIndex(int *arr, int n);
void heapSortOnce(int *arr, int index);
int main(void) {
int n;
cin >> n;
int *init = new int[n];
int *arr = new int[n];
for(int i = 0; i < n; ++i)
cin >> init[i];
for(int i = 0; i < n; ++i)
cin >> arr[i];
if(isHeapSort(init, arr, n)) {
cout << "Heap Sort" << endl;
heapSortOnce(arr, getNextHeapSortIndex(arr, n));
} else
cout << "Insertion Sort" << endl;
cout << arr[0];
for(int i = 1; i < n; ++i)
cout << " " << arr[i];
delete[] init;
delete[] arr;
return 0;
}
/*
* 1. 從前面找第一個反序的元素索引 -> 有序子列元素個數。
* 2. 判斷從該索引開始，是否與原始數列一緻。若一緻，是插入排序。
*/
bool isHeapSort(int *init, int *arr, int n) {
int len = 1; //記錄插入排序中，有序子列的個數。
for(int i = 0; i < n - 1; ++i) {
if(arr[i] > arr[i + 1]) {
len = i + 1;
break;
}
}
for(int i = len; i < n; ++i)
if(arr[i] != init[i]) return true;
sort(arr, arr + len + 1); //若是插入排序，直接在這裡完成下一趟插入。
return false;
}
//傳回下一次進行堆排序操作的元素的下标。
int getNextHeapSortIndex(int *arr, int n) {
int heap = arr[0];
for(int i = 1; i < n; ++i) {
if(arr[i] > heap) return i - 1;
}
return n - 1; //最大堆，未排序。
}
void heapSortOnce(int *arr, int index) {
swap(arr[0], arr[index]);
int size = index - 1;
//下濾。
int tmp = arr[0];
int parent = 0;
int child;
for(; parent*2 + 1 <= size; parent = child) {
child = parent * 2 + 1;
if(child < size && arr[child] < arr[child + 1]) ++child;
if(tmp > arr[child]) break;
else arr[parent] = arr[child];
}
arr[parent] = tmp;
} 複制
