大型网站开发的主流语言,英文网站设计理念,免费注册163免费邮箱个人,景点网站建设排序
排序和排列是算法题目常见的基本算法。几乎每次蓝桥杯软件类大赛都有题目会用到排序或排列。常见的排序算法如下。 第(3)种排序算法不是基于比较的#xff0c;而是对数值按位划分#xff0c;按照以空间换取时间的思路来排序。看起来它们的复杂度更好#xff0c;但实际…排序
排序和排列是算法题目常见的基本算法。几乎每次蓝桥杯软件类大赛都有题目会用到排序或排列。常见的排序算法如下。 第(3)种排序算法不是基于比较的而是对数值按位划分按照以空间换取时间的思路来排序。看起来它们的复杂度更好但实际上它们的应用环境比较苛刻在很多情况下并不比前几种排序算法更好。
排序是基本的数据处理读者需要认真体会这些算法的思路和操作方法。不过在算法竞赛中一般不需要手动编写这些排序算法而是直接使用库函数例如C的sort()函数。 STL的排序函数sort()有以下两种定义 (1)void sort (RandomAccessIterator first, RandomAccessIterator last); (2)void sort (RandomAccessIterator first, RandomAccessIterator last,Compare comp); 简称前闭后开。
sort()支持从大到小的排序也支持从小到大的排序。sort()自带4种排序less、greater、less_equal、greater_equal。默认情况下sort()按从小到大进行排序less可以不写。 代码演示
#includebits/stdc.h
using namespace std;
bool my_less(int i, int j) {return (i j); //自定义小于函数
}
bool my_greater(int i, int j) {return (i j); //自定义大于函数
}
int main () {int a[] {3,7,2,5,6,8,5,4};sort(a,a4); //对前4个数排序结果2 3 5 7 6 8 5 4for(int i0; i8; i) couta[i] ;cout”\n”; //下面可以复制这一行输出sort(a,a8,lessint()); //从小到大排序结果2 3 4 5 5 6 7 8sort(a,a8,my_less); //自定义排序结果2 3 4 5 5 6 7 8sort(a,a8,greaterint()); //从大到小排序结果8 7 6 5 5 4 3 2sort(a,a8,my_greater); //自定义排序结果8 7 6 5 5 4 3 2vectorint c {1,2,3,4,5,6,7,8};sort(c.begin(),c.end(),my_greater); //结果8 7 6 5 4 3 2 1for(int i0; ic.size(); i) coutc[i] ;cout \n;string shello world; sort(s.begin(),s.end());couts; //输出dehllloorw。注意第一个是空格return 0;
}
C的sort()有两个优点能在原数组上排序不需要新的空间能在数组的局部区间上排序。 例题1-统计数字 代码
#includebits/stdc.h
using namespace std;
int nums[200010];//n200000我们多申请一点多10就行了。
int main() {int n;scanf(%d,n);for(int i 1; i n; i) scanf(%d,nums[i]);sort(nums1, nums1n);int cnt 0;for(int i 1; i n; i) {cnt;//某个数出现的次数if(nums[i] ! nums[i1]) {printf(%d %d\n, nums[i], cnt); //说明这个数结束了轮到下一个数了记录一次cnt 0; //置0重新计数}}
} 例题2-错误票据 题目分析本题是简单题解题思路是读取所有数字先排序然后查找丢失的数字和重复的数字。本题的麻烦之处是输入的处理。
代码
#includebits/stdc.h
using namespace std;
const int N 1e410;//申请的数组比预期的要大一点。
int a[N];
int main() {int n;cin n;int cnt 0;while(scanf(%d, a[cnt]) ! EOF) cnt; //注意读数据的写法下面会讲解sort(a, acnt);//排序int ans1, ans2;for(int i 1; i cnt; i) {if(a[i] - a[i-1] 1) ans1 a[i-1]1; //查找断号if(a[i] a[i-1]) ans2 a[i]; //查找重号}cout ans1 ans2;return 0;
}
比赛经常有这样的代码while(scanf(“%d%d”)!EOF)这玩意啥意思呢首先scanf你写while里就很奇怪了初学者表示没见过这么嵌套写的再加个EOF更离谱了。
首先这个代码scanf能写while里是因为scanf(“%d%d”)!EOF本身是个逻辑判断也就是真或者假所以可以作为条件判断写到while里。
EOF到底啥玩意
您不妨打开我们最常用的stdio.h这个头文件然后搜索EOF即可发现答案蓝桥杯指定编译器devcpp中怎么打开这个文件呢按住ctrl然后用鼠标点击stdio.h即可进入
找到了 EOF其实就是-1
也就是说EOF就是个数字被定义为-1而已
在我们进行包括scanf等的输入函数使用时其实用户在cmd中的输入实际是存放于缓冲区当中当用户键入回车那一瞬间之前输入的数据才会被存进去而这里无论是单个字符还是字符串我们都知道scanf的返回值呢是表示成功接受到的对象的个数那这里如果遇到特殊情况比如缓冲区文件流满等问题那么scanf将如何处理呢答案是返回-1 ! 这里不光是scanf返回值为个数的函数遇到文件流满大多都会返回-1所以这个-1用的比较多那么stdio.h就索性专门定义一个宏来表示取End Of File(文件末尾的意思)的前三个字母即组成EOF所以也就有了 #define EOF (-1) 这样的话 例题3.结构体排序 代码
#includebits/stdc.h
using namespace std;
struct stu {int id; //学号int c,m,e; //语文、数学、英语成绩int sum;
} st[305];
bool cmp(stu a,stu b) {if(a.sum b.sum) return True;else if(a.sum b.sum) return False;else { //a.sum b.sumif(a.c b.c) return True;else if(a.c b.c) return False;else { //a.c b.cif(a.id b.id) return False;else return True;}}
}
int main() {int n;cinn;for(int i1; in; i) {st[i].id i; //学号cin st[i].c st[i].m st[i].e;st[i].sum st[i].c st[i].m st[i].e; //总分}sort(st1,st1n,cmp);for(int i1; in; i) coutst[i].id st[i].sum endl;return 0;
}
