蓝桥杯：C++排序
排序
排序和排列是算法题目常见的基本算法。几乎每次蓝桥杯软件类大赛都有题目会用到排序或排列。常见的排序算法如下。
第(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可以不写。
代码演示：
#include<bits/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,a+4); //对前4个数排序，结果：2 3 5 7 6 8 5 4for(int i=0; i<8; i++) cout<<a[i]<< " ";cout<<”\n”; //下面可以复制这一行输出sort(a,a+8,less<int>()); //从小到大排序，结果：2 3 4 5 5 6 7 8sort(a,a+8,my_less); //自定义排序，结果：2 3 4 5 5 6 7 8sort(a,a+8,greater<int>()); //从大到小排序，结果：8 7 6 5 5 4 3 2sort(a,a+8,my_greater); //自定义排序，结果：8 7 6 5 5 4 3 2vector<int> 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 i=0; i<c.size(); i++) cout<<c[i]<< " ";cout<< "\n";string s="hello world"; sort(s.begin(),s.end());cout<<s; //输出：dehllloorw。注意第一个是空格return 0;
}C++的sort()有两个优点：能在原数组上排序，不需要新的空间；能在数组的局部区间上排序。
例题1-统计数字
代码：
#include<bits/stdc++.h>
using namespace std;
int nums[200010];//n<=200000，我们多申请一点，多10就行了。
int main() {int n;scanf("%d",&n);for(int i = 1; i <= n; i++) scanf("%d",&nums[i]);sort(nums+1, nums+1+n);int cnt = 0;for(int i = 1; i <= n; i++) {cnt++;//某个数出现的次数if(nums[i] != nums[i+1]) {printf("%d %d\n", nums[i], cnt); //说明这个数结束了，轮到下一个数了，记录一次cnt = 0; //置0，重新计数}}
}例题2-错误票据
题目分析：本题是简单题，解题思路是读取所有数字，先排序，然后查找丢失的数字和重复的数字。本题的麻烦之处是输入的处理。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;//申请的数组比预期的要大一点。
int a[N];
int main() {int n;cin >> n;int cnt = 0;while(scanf("%d", &a[cnt]) != EOF) cnt++; //注意读数据的写法，下面会讲解sort(a, a+cnt);//排序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.结构体排序
代码：
#include<bits/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;cin>>n;for(int i=1; i<=n; 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(st+1,st+1+n,cmp);for(int i=1; i<=n; i++) cout<<st[i].id<<" "<<st[i].sum<< endl;return 0;
}