当前位置：首页 > 编程日记 > 正文

1098 Insertion or Heap Sort 需再做

编程日记 2024-09-06 16:30:00

1. 应该还做过一道类似的题目，也是要求判断属于哪种排序的中间过程，并要求写出下一轮排序结果，这次的进步是上来就知道用向量存数据，这样方便直接比较，而且下标0不能存元素，因为堆排序的堆是一个完全二叉树，只有下标从1开始，才符合左子节点为父节点下标*2的规律。

2. 所以基础知识没啥好说，得会插排和堆排，插排有一个地方很容易错，就是判断插入位置的while条件，应该是temp和vi[j-1]而不是和vi[j]比较，如果是temp小就继续向前。

3. 另外是堆排序在每一轮排序中判断和对照向量是否相等的时机，我们知道，堆排序每一轮是先让当前未排序的最后一个元素和第一个元素交换，然后对第一个元素进行向下调整，对照时机是在这两步都完成后，而不是在这两者之间。

4. 有过纠结：这个排序到底让我用最大堆还是最小堆，现在看来由于是增序排列，所以是最大堆。

又重新做了一遍，新增两个注意点：

5. 既然downAdjust函数都写出了，建堆就用从最后一个叶子结点开始，一直往上数到头节点，向下调整。不要用那个从第一个节点开始，看最上能上到哪的简易建堆方式。

6. 封装每个函数，都要关注返回值有没有。

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 110;vector<int> init,comp;//初始序列，对照序列
vector<int> procByIn;//插排处理序列
vector<int> procByHe;//堆排序处理序列 
int n;//元素个数
int heapRes = false;void downAdjust(int low,int high){int i = low;int j = i*2;while(j<=high){if(j+1<=high&&procByHe[j+1]>procByHe[j])j=j+1;if(procByHe[j]>procByHe[i]){swap(procByHe[i],procByHe[j]);i = j;j = i*2;}else break;}
}void createHeap(){for(int i=n/2;i>=1;i--){downAdjust(i,n);}
}void heapSort(){createHeap();for(int i=n;i>=1;i--){swap(procByHe[1],procByHe[i]);downAdjust(1,i-1);	if(procByHe==comp){printf("Heap Sort\n");	heapRes = true;//提前进入下一轮 swap(procByHe[1],procByHe[i-1]);downAdjust(1,i-2);for(int j=1;j<=n;j++){printf("%d",procByHe[j]);if(j!=n)printf(" ");}printf("\n");break;}}
}void insertSort(){bool canPrint = false;for(int i=2;i<=n;i++){int j = i;int temp = procByIn[i];while(j>1&&temp<procByIn[j-1]){procByIn[j] = procByIn[j-1];j--;}procByIn[j] = temp;if(canPrint){for(int k=1;k<=n;k++){printf("%d",procByIn[k]);if(k!=n)printf(" ");}printf("\n");break;}if(procByIn==comp){printf("Insertion Sort\n");canPrint = true;}}
} int main(){scanf("%d",&n);int num;init.push_back(0);//占位 for(int i=0;i<n;i++){scanf("%d",&num);init.push_back(num);}comp.push_back(0);for(int i=0;i<n;i++){scanf("%d",&num);comp.push_back(num); } procByHe = init;heapSort(); if(!heapRes){//不是堆排序，再进行插入排序 procByIn = init;insertSort();}return 0;
}

https://www.dkcj.cn/info/17560.html

1098 Insertion or Heap Sort 需再做

相关文章：

基于node.js的压缩合并安装

jenkins 修改工作目录

破一个行业ERP的感想

1034 Head of a Gang(图的DFS解法) 擦边大法好

Android定位方式和测试方法

vue el-form鼠标事件导致页面刷新解决方案；vue 阻止多次点击提交数据通用方法...

[转]wxODBC(wxWidgets)中使用驱动程序方式打开数据库

1076 Forwards on Weibo

2014年个人工作总结

DAL(数据库访问层)

Navicat for Oracle

1013 Battle Over Cities(图的DFS解法)

你必须了解的微服务架构设计的10个要点！

企业信息化中常见决策点应对

WebView调试

1013 Battle Over Cities(并查集解法)

FastDFS为什么要结合Nginx？

STL容器[34]

企业可视化报表工具选型经验分享

1003 Emergency(Dijkstra，Bellman-Ford，SPFA三种解法)

存储过程4-前台

安卓学习-其他-文件读写

X5同层播放器应用实践

1007 Maximum Subsequence Sum(两种思路)

C#学习-EF在三层中使用

各大IT公司笔试真题汇总开发人员一定要加入收藏夹的网站(收藏)

Python编写Hive UDF

1045 Favorite Color Stripe(LIS解法)

5.8fork父子进程

word表格自动编号