题目描述
blablabla
样例
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
int Origin[N],tempOri[N],Changed[N];
int n;
bool isSame(int A[],int B[])
{
for(int i=1;i<=n;i++)
{
if(A[i]!=B[i]) return false;
}
return true;
}
void showarray(int A[])
{
for(int i=1;i<=n;i++)
{
printf("%d",A[i]);
if(i!=n) printf(" ");
}
printf("\n");
}
bool insertSort()
{
bool flag=false;
for(int i=2;i<=n;i++)//进行n-1趟排序
{
if(i!=2&&isSame(tempOri,Changed)==true)
{
flag=true;
}
sort(tempOri,tempOri+i+1);//sort排序到【a,b-1】!!
if(flag==true) return true;
// int temp=A[i],j=i;
// while(j>1&&temp<a[j])
// {
// a[j]=a[j-1];
// j--;
// }
// a[j]=temp;
}
return false;
}
void downAdjust(int low,int high)//大根堆向下调整
{
int i=low,j=2*i;
while(j<=high)
{
if(j+1<=high){
if(tempOri[j+1]>tempOri[j]) j=j+1;
}
if(tempOri[i]<tempOri[j])
{
swap(tempOri[i],tempOri[j]);
i=j;
j=2*i;
}
else break;
}
}
void heapSort()
{
bool flag=false;
for(int i=n/2;i>=1;i--)
{
downAdjust(i,n);//建堆
}
for(int i=n;i>=1;i--)
{
if(i!=n&&isSame(tempOri,Changed)==true)
{
flag=true;
}
swap(tempOri[1],tempOri[i]);
downAdjust(1,i-1);//not downAdjust(1,i);
if(flag==true) {
showarray(tempOri);
return;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&Origin[i]);
tempOri[i]=Origin[i];
}
for(int i=1;i<=n;i++)
{
scanf("%d",&Changed[i]);
}
if(insertSort())
{
printf("Insertion Sort\n");
showarray(tempOri);
}
else
{
printf("Heap Sort\n");
for(int i=1;i<=n;i++)
{
tempOri[i]=Origin[i];
}//还原数组
heapSort();
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla