浙大数据结构：09-排序3 Insertion or Heap Sort

这个题跟上个题差不多，只不过是换成了堆排序而已
机翻
在这里插入图片描述

1、条件准备

跟之前一样，oldnum数组存旧数组，newnum数组存新数组

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'int n;
vector<int> oldnum;
vector<int> newnum;

2、主函数

先判断是否为插入排序，否则就进入堆排序，并迭代输出

int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++){int a;cin>>a;oldnum.push_back(a);}for(int i=0;i<n;i++){int a;cin>>a;newnum.push_back(a);}if(!judgeinsert())heap_sort();return 0;
}

3、judgeinsert函数

递增数组找到尽头再看看后面元素是否匹配。不匹配则为堆排序，再插入一次输出

bool judgeinsert()
{int tag=0;for(int i=0;i<n-1;i++)if(newnum[tag]<=newnum[tag+1])tag++;tag++;for(int i=tag;i<n;i++)if(oldnum[i]!=newnum[i])return 0;cout<<"Insertion Sort\n";int tmp=newnum[tag]; int i;for( i=tag-1;i>=0&&newnum[i]>tmp;i--)newnum[i+1]=newnum[i];newnum[i+1]=tmp;for(int i=0;i<n-1;i++)cout<<newnum[i]<<' ';cout<<newnum[n-1];return 1;
}

4、sift_down函数

建立大根堆所要调用的函数

void sift_down(vector<int>&arr, int start, int end) {// 计算父结点和子结点的下标int parent = start;int child = parent * 2 + 1;while (child <= end) {  // 子结点下标在范围内才做比较// 先比较两个子结点大小，选择最大的if (child + 1 <= end && arr[child] < arr[child + 1]) child++;// 如果父结点比子结点大，代表调整完毕，直接跳出函数if (arr[parent] >= arr[child])return;else {  // 否则交换父子内容，子结点再和孙结点比较swap(arr[parent], arr[child]);parent = child;child = parent * 2 + 1;}}
}

5、堆排序

先建立堆，然后每次把最大的根放在最后，判断完成当前操作是否与newnum数组一样，一样则跳出，再进行一次迭代即可输出

void heap_sort() {cout<<"Heap Sort"<<endl;// 从最后一个节点的父节点开始 sift down 以完成堆化 vector<int> arr=oldnum;for (int i = (n - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, n - 1);// 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕int i; int f=1;for ( i = n - 1; i > 0; i--) {f=1;swap(arr[0], arr[i]);sift_down(arr, 0, i - 1);for(int j=0;j<n;j++)if(newnum[j]!=arr[j]){f=0;break;}if(f)break;}i--;swap(arr[0], arr[i]);sift_down(arr, 0, i - 1);for(int i=0;i<n-1;i++)cout<<arr[i]<<' ';cout<<arr[n-1];
}

6、总结

这道题在上一题的基础上完成，难度适中
完整代码如下

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'int n;
vector<int> oldnum;
vector<int> newnum;bool judgeinsert()
{int tag=0;for(int i=0;i<n-1;i++)if(newnum[tag]<=newnum[tag+1])tag++;tag++;for(int i=tag;i<n;i++)if(oldnum[i]!=newnum[i])return 0;cout<<"Insertion Sort\n";int tmp=newnum[tag]; int i;for( i=tag-1;i>=0&&newnum[i]>tmp;i--)newnum[i+1]=newnum[i];newnum[i+1]=tmp;for(int i=0;i<n-1;i++)cout<<newnum[i]<<' ';cout<<newnum[n-1];return 1;
}void sift_down(vector<int>&arr, int start, int end) {// 计算父结点和子结点的下标int parent = start;int child = parent * 2 + 1;while (child <= end) {  // 子结点下标在范围内才做比较// 先比较两个子结点大小，选择最大的if (child + 1 <= end && arr[child] < arr[child + 1]) child++;// 如果父结点比子结点大，代表调整完毕，直接跳出函数if (arr[parent] >= arr[child])return;else {  // 否则交换父子内容，子结点再和孙结点比较swap(arr[parent], arr[child]);parent = child;child = parent * 2 + 1;}}
}void heap_sort() {cout<<"Heap Sort"<<endl;// 从最后一个节点的父节点开始 sift down 以完成堆化 vector<int> arr=oldnum;for (int i = (n - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, n - 1);// 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕int i; int f=1;for ( i = n - 1; i > 0; i--) {f=1;swap(arr[0], arr[i]);sift_down(arr, 0, i - 1);for(int j=0;j<n;j++)if(newnum[j]!=arr[j]){f=0;break;}if(f)break;}i--;swap(arr[0], arr[i]);sift_down(arr, 0, i - 1);for(int i=0;i<n-1;i++)cout<<arr[i]<<' ';cout<<arr[n-1];
}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++){int a;cin>>a;oldnum.push_back(a);}for(int i=0;i<n;i++){int a;cin>>a;newnum.push_back(a);}if(!judgeinsert())heap_sort();return 0;
}