PAT——1098 Insertion or Heap Sort 甲级（超详细注释）

• 题目
• 题意
• 代码思路
• AC代码
• 参考

https://pintia.cn/problem-sets/994805342720868352/problems/994805368847187968

首先，不了解堆排序流程的同学可以看看我的第二篇参考文章（插入排序较为简单，不会的同学自行学习）

题目给出两个序列a、b，a为最初序列，b为排序过的序列，问排序方式是插入排序还是堆排序，并输出下一步的排序结果

代码思路详见参考文章第一篇

需要说明的是，low参数的使用我放在了对i的赋初值上，这样至少用到了low；至于从小到大还是从大到小，我建议大家看一下参考文章第二篇的图文讲解，结合那个讲解相信你自己就能真正理解了

#include
using namespace std;
//堆排序最开始要先构建大顶堆，但因为题目中至少已经排序了以一次，说明题目已经完成的大顶堆的准备并开始排序了
//所以我们只需要完成后面的步骤就好
void downAdjust(vector &b,int low,int high)
{
	int i=low,j=low*2;
	while(j<=high)
	{
		if(j+1<=high&&b[j]b[j]) return;//注意，这里不写=是因为堆排序不稳定，相等数字的相对位置会发生变化
		swap(b[i],b[j]);
		i=j,j=i*2;
	}	
} 
int main()
{
	int n,p=2;//序列下标从1开始，要从第二个数字开始和前一个数字比，所以p=2
	scanf("%d",&n);
	vector a(n+1),b(n+1);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]); 
	while(p<=n&&b[p-1]<=b[p]) p++;//这里的 a[p-1]<=a[p]之所以有等于号是因为，插入排序是稳定的，相同数字的相对位置不变 
	int index=p;//index的位置是第一个不满足从小到大排序的数字，也就是下一次插入排序的右边界
	while(p<=n&&a[p]==b[p]) p++;
	//插入排序从index开始的数字位置都是不变的（因为没轮到它们排序），否则就是堆排序了 
	if(p==n+1)
	{
		printf("Insertion Sortn");
		sort(b.begin(),b.begin()+index+1);
	}
	else
	{
		printf("Heap Sortn");
		p=n;
		while(p>2&&b[p]>b[1]) p--; 
		swap(b[1],b[p]);
		downAdjust(b,1,p-1);
	}
	for(int i=1;i<=n;i++)
	{
		if(i!=1) printf(" ");
		printf("%d",b[i]);
	}
}

1098. Insertion or Heap Sort (25)-PAT甲级真题（堆排序）

堆排序算法（图解详细流程）