蓝桥杯（排序）

下面介绍几种常用的排序方法

以P1177模板题为例

（1）插入排序

将数组第一个元素化为已排序区间 从第 2 个元素（未排序区间第一个）开始，逐个取出元素作为待插入元素 将待插入元素与前面已排序区间的元素从后往前作比较若已排序元素更大则将其后移一位直到找到待插入元素的正确位置 完成插入

时间复杂度：最好情况是有序不需要移动比较n-1次O(n) 最坏是逆序为O(n^2) 平均为O(n^2)

空间复杂度：O（1）

代码如下

（2）选择排序

在未排序序列中找到最小元素； 将其与未排序部分的第一个元素交换； 重复上述过程，每次缩小未排序区间，直到整个数组有序

时间复杂度：最好与最坏都是O(n^2)

空间复杂度：O(1)

（3）冒泡排序

将数组视为整体，每一轮从左到右相邻元素两两比较，如果顺序错误（升序则前 > 后）就交换位置；每一轮遍历后，未排序区间的最大元素会像气泡一样 “浮” 到未排序区间的末尾（即已排序区间的开头）每一轮将待排序区间中的最值放到最后面 优化版可以在中途判断是否已经有序

时间复杂度：无优化版：最好==最坏==O(n^2) 都需要一直比较直到结束

优化版：最好=O(n) 最坏=O(n^2) 最好情况是数组完全有序

空间复杂度：O(1)

无优化版：

优化版：如果在一轮中没有发生交换那么直接跳出循环说明已经有序

（4）归并排序

基于「分治思想」，将数组递归拆分为两个子数组，直到子数组长度为 1；再将两个有序子数组合并为一个有序数组。

时间复杂度：O(n*logn)

空间复杂度: O(n)开辟了一个临时数组

（5）快速排序

基于「分治思想」，选一个元素作为「基准值 pivot」，将数组分为「小于 pivot」「等于 pivot」「大于 pivot」三部分；递归处理左右子数组。

时间复杂度：O(n*logn)

空间复杂度: O(1)

(6)堆排序

以升序为例 建立大根堆 如果要降序那就建立小根堆

利用「堆（完全二叉树）」的特性（大顶堆：父节点 > 子节点；小顶堆：父节点 < 子节点），将数组构建为大顶堆，反复提取堆顶元素（最大值）并调整堆。

时间复杂度:O(n*logn)

空间复杂度:O（1）

P1152 欢乐的跳

用了set容器 支持升序和去重比较快 用set<int, greater<int>> s;可以支持降序 用multiset支持不去重

P1271选举学生会

使用multiset容器

P1923求第k小的数

题目数据较大需要关闭流同步

cin.tie(nullptr);
ios::sync_with_stdio(false)；

P1781宇宙总统

首先定义一个结构体存储字符串类型的票数和id 然后进行比较 比较判断传入的是一整个return的值

只要size不同就判断跟max相比谁的票数更大 size相同就用字符串自带的比较 比首位

P1093奖学金

sort排序的用法 对结构体自定义规则的排序 sort(起始地址，终止地址，自定义比较规则)

大于1e7会超时

sort排序下标从0开始 从下列代码学习 相当于cmp是裁判sort排序时，会不断拿出两个元素 x 和 y，丢给cmp这个专属裁判，问：「x 和 y 相比，x 是否有资格排在 y 的前面？」裁判回答true x排前否则换成y排前

P2676BookShelf

sort排序的一个降序用法 sort(a,a+n,greater<int>())

P1116车厢重组

使用优化版冒泡排序

P1068分数线划定

取整的函数：向下取整用floor()，向上取整用ceil()，四舍五入用round()，截断小数用trunc()或(int)强制转换；

还是用之前结构体自定义规则sort排序的方法

P5134攀爬者

与上面题目如出一辙 sort对结构体自定义规则排序 保留三位小数用fixed setprecision(3)

P1104生日

与之前的大致相同 但是要命名一个id保证输入靠后的先输出

以上是排序题单中的例题还有排序方法、sort函数的使用、set容器使用等方法