目的:通过初始序列,判断中间序列是插入排序还是堆排序。再输出下一步
输入:
N 数字个数
两个序列
输出:
插入排序还是堆排序
算法:
由于答案唯一。所以,先判断是否为插入排序。若不是,就一定为堆排序。
插入排序中间序列的特点。前面一部分从小到大排列好的。后面一部分与原序列相同。
这里有一个小问题就是。如果原序列有一些位置以经排列好了。比图原序列为2 3 4 1 7 6.中间序列为2 3 4 1 7 6.那么这是3步的中间序列。也就是下一个就会改变了。
所以要找到最大的某一个位置,这个位置之前为排序好的,这个位置之后与原序列相同。
/*#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int N;
vector<int> v1,v2,heap;
void downjust(int low,int high)
{
int i = low,j = i*2;
while(j<=high)
{
//找出两个孩子结点中的最大值
if(j+1<=high&&heap[j+1]>heap[j])
{
j = j+1;
}
//如果孩子结点中的最大值比欲调整的结点大
if(heap[j]>heap[i])
{
swap(heap[i],heap[j]);
i = j;
j = j*2;
}else
{
break;//若有一个不满足,那么证明后面的都已经调整好了
}
}
}
void creat()
{
for(int i=N/2;i>0;i--)
{
downjust(i,N);
}
}
void heapsort()
{
bool flag = false;
for(int i=N;i>1;i--)
{
swap(heap[1],heap[i]);
downjust(1,i-1);
if(flag==true)
{
return;
}
if(heap==v2)
{
flag = true;
}
}
}
int main()
{
scanf("%d",&N);
v1.resize(N+1);
v2.resize(N+1);
for(int i=1;i<=N;i++)
{
scanf("%d",&v1[i]);
}
for(int i=1;i<=N;i++)
{
scanf("%d",&v2[i]);
}
heap = v1;
int k = 0;
for(int i=N;i>0;i--)
{
if(heap[i]!=v2[i])
{
k = i;
break;
}
}
bool flag = false;
sort(heap.begin()+1,heap.begin()+k+1);
if(heap==v2)
{
flag = true;
}
if(flag==true)
{
printf("Insertion Sort\n");
while(heap==v2&&k<N)
{
sort(heap.begin()+1,heap.begin()+k+1);
k++;
}
for(int i=1;i<=N;i++)
{
if(i!=1) printf(" ");
printf("%d",heap[i]);
}
}else
{
printf("Heap Sort\n");
heap = v2;
int p = N;
while(heap[1]<=heap[p]&&p>2)p--;
swap(heap[1],heap[p--]);
downjust(1,p);
for(int i=1;i<=N;i++)
{
if(i!=1) printf(" ");
printf("%d",heap[i]);
}
}
return 0;
}
*/#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a,b,c;
int n;
void downadjust(int low,int high)
{
int i = low,j = i*2;
while(j<=high)
{
if(j+1<=high&&b[j+1]>b[j])
{
j = j+1;
}
if(b[j]>b[i])
{
swap(b[i],b[j]);
i = j;
j = j*2;
}else
{
break;
}
}
}
void creat()
{
for(int i=n/2;i>=1;i--)
{
downadjust(i,n);
}
}
void heaporder()
{
for(int i=n;i>=1;i--)
{
swap(b[1],b[i]);
downadjust(1,i-1);
if(b==c)
{
swap(b[1],b[i-1]);
downadjust(1,i-2);
break;
}
}
}
int main()
{
scanf("%d",&n);
a.resize(n+1);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
b = a;
c.resize(n+1);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
bool flag = false;
for(int i=1;i<=n;i++)
{
sort(a.begin()+1,a.begin()+i);
if(a==c)
{
flag = true;
continue;//这里跳过了
}
if(flag == true)
{
break;
}
}
if(flag == true)
{
printf("Insertion Sort\n");
for(int i=1;i<=n;i++)
{
printf("%d",a[i]);
if(i!=n)
printf(" ");
}
}else
{
printf("Heap Sort\n");
creat();
heaporder();
for(int i=1;i<=n;i++)
{
printf("%d",b[i]);
if(i!=n)
printf(" ");
}
}
return 0;
}
反思:堆排序有些生疏了。还有,找到插入排序的指定位置有些问题。最好的方法是,遍历中间序列,找到一个位置,后一个元素小于前一个元素。这里就是分界线。再对原序列按照这个位置排序。比对两个序列是否一样。一样就是插入排序。
还有堆排序。不用从头再来。直接对中间序列下调整一次。分界线在,从后往前遍历,第一个小于中间序列第一个元素的位置。