09-排序3 Insertion or Heap Sort (25分)
09-排序3 Insertion or Heap Sort (25分)
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;
} 
