蓝桥杯（排序）

下面介绍几种常用的排序方法以P1177模板题为例1插入排序将数组第一个元素化为已排序区间 从第 2 个元素未排序区间第一个开始逐个取出元素作为待插入元素 将待插入元素与前面已排序区间的元素从后往前作比较若已排序元素更大则将其后移一位直到找到待插入元素的正确位置 完成插入时间复杂度最好情况是有序不需要移动比较n-1次O(n) 最坏是逆序为O(n^2) 平均为O(n^2)空间复杂度O1代码如下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)空间复杂度:O1P1152 欢乐的跳用了set容器 支持升序和去重比较快 用setint, greaterint 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排前P2676BookShelfsort排序的一个降序用法 sort(a,an,greaterint())P1116车厢重组使用优化版冒泡排序P1068分数线划定取整的函数向下取整用floor()向上取整用ceil()四舍五入用round()截断小数用trunc()或(int)强制转换还是用之前结构体自定义规则sort排序的方法P5134攀爬者与上面题目如出一辙 sort对结构体自定义规则排序 保留三位小数用fixed setprecision(3)P1104生日与之前的大致相同 但是要命名一个id保证输入靠后的先输出以上是排序题单中的例题还有排序方法、sort函数的使用、set容器使用等方法