浙大数据结构：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;
}
原文地址：https://blog.csdn.net/qq_74924951/article/details/142927333
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！