题目链接:Insertion or Heap Sort 大意:给你两个数列,第二个是第一个通过某种排序算法 过程中产生的一个状态序列。让你判断此时使用的是插入排序还是堆排序 ,并且输出下一个状态的序列。 很暴力的解法,把排序的每一个状态都记录下来,然后一一比对,最后输出下一个状态序列。我们直到插入排序时间复杂度是O(N^2),但是本题数据量也较少,n<=100。所以没有问题。不论堆排序 还是插入排序,记录的序列最多是n个。然后和一个长度为n的序列进行比对的话,时间复杂度也是O(N^2)的,所以铁定不会超时的。 本题的考点应该在于手写插入排序和堆排序 。堆排序 的详解见这篇博客Heap Sort AC 代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std ;
bool debug = false ;
vector <int > get_row(int * data, int n)
{
vector <int > row;
for (int i=0 ;i<n;i++)
{
row.push_back(data[i]);
}
return row;
}
void display(int * data, int n)
{
for (int i=0 ;i<n;i++)
{
cout <<data[i]<<" " ;
}
cout <<endl;
}
void display(vector <int > data, int n)
{
for (int i=0 ;i<n;i++)
{
cout <<data[i];
if (i!=(n-1 ))
{
cout <<" " ;
}
}
cout <<endl;
}
vector <vector <int > > insert_sort(int * data, int n)
{
vector <vector <int > > res;
bool not_change[n];
memset (not_change, 0 , sizeof (not_change));
for (int i=1 ;i<n;i++)
{
int target = data[i];
if (debug)
cout <<"target is " <<target<<endl;
for (int j=i;j>=0 ;j--)
{
if (j!=0 && data[j-1 ] >= target)
{
data[j] = data[j-1 ];
}else {
data[j] = target;
break ;
}
}
if (debug)
display(get_row(data,n), n);
res.push_back(get_row(data,n));
}
return res;
}
vector <vector <int > > heap_sort(int * data, int n)
{
vector <vector <int > > res;
for (int i=n-1 ;i>=0 ;i--)
{
int max_index = i;
for (int j=i;j>=0 ;j--)
{
if (data[j] > data[max_index])
{
max_index = j;
}
}
if (max_index != i)
{
int temp = data[i];
data[i] = data[max_index];
data[max_index] = temp;
}
if (debug)
display(get_row(data,n), n);
res.push_back(get_row(data, n));
}
return res;
}
void HeapAdjust(int array [],int i,int nLength)
{
int nChild;
int nTemp;
for (;2 *i+1 <nLength;i=nChild)
{
nChild=2 *i+1 ;
if (nChild<nLength-1 &&array [nChild+1 ]>array [nChild])++nChild;
if (array [i]<array [nChild])
{
nTemp=array [i];
array [i]=array [nChild];
array [nChild]=nTemp;
}
else break ;
}
}
vector <vector <int > > HeapSort(int array [],int length)
{
vector <vector <int > > res;
int i;
for (i=length/2 -1 ;i>=0 ;--i)
HeapAdjust(array ,i,length);
for (i=length-1 ;i>0 ;--i)
{
array [i]=array [0 ]^array [i];
array [0 ]=array [0 ]^array [i];
array [i]=array [0 ]^array [i];
HeapAdjust(array ,0 ,i);
res.push_back(get_row(array , length));
}
return res;
}
int max_n = 105 ;
int find_in_vector(vector <vector <int > > record, int * target, int n)
{
for (int i=0 ;i<record.size();i++)
{
bool flag = true ;
for (int j=0 ;j<n;j++)
{
if (target[j] != record[i][j])
{
flag = false ;
break ;
}
}
if (flag)
{
return i;
}
}
return -1 ;
}
int main()
{
int n;
cin >>n;
int data[max_n];
int heap_data[max_n];
int target_sequence[max_n];
for (int i=0 ;i<n;i++)
{
cin >>data[i];
heap_data[i] = data[i];
}
for (int i=0 ;i<n;i++)
{
cin >>target_sequence[i];
}
vector <vector <int > > insert_vector = insert_sort(data, n);
vector <vector <int > > heap_vector = HeapSort(heap_data, n);
int insert_index = find_in_vector(insert_vector, target_sequence, n);
if (insert_index != -1 )
{
cout <<"Insertion Sort" <<endl;
display(insert_vector[insert_index+1 ],n);
}
int heap_index = find_in_vector(heap_vector, target_sequence, n);
if (heap_index != -1 )
{
cout <<"Heap Sort" <<endl;
display(heap_vector[heap_index+1 ],n);
}
return 0 ;
}