该笔记还未完成整理,待日后继续整理……
该笔记目前直接复制的之前的笔记,还未调整格式。页面格式、内容、链接等可能存在混乱错误……
排序
不考虑算法
- 选择排序、冒泡排序、插入排序 $O(n^2)$
- 计数排序、基数排序、桶排序 $O(n+w)$
- 希尔排序、锦标赛排序
快速排序
应用
- 寻找第k大的数
归并排序
应用
- 寻找逆序对
可见之前笔记。
(有关逆序对的问题还可以用树状数组或线段树来解决。)- 对于逆序对问题的抽象:
- 询问最少经过几次(可能为相邻元素交换)交换,可使数列有序。
如果限制了为相邻元素交换,最开始很容易想到采用冒泡排序来做,但这样$O(n^2)$很容易TLE……
发现即便是相邻交换,也是因为存在了逆序对才交换的……
而每次交换后,能且仅能消除一个逆序对……
要使序列达到最终有序,则肯定需要消除全部逆序对……
故此类题目仍为求逆序对,且答案就为逆序对个数……
如果没有限制相邻元素交换,那么处理一位数,就能消除这位数的所有逆序对个数(与相邻交换的区别)
所以就变成了找存在逆序对的位(简称:逆位)的个数。 - 模板题:
P1908 逆序对
- 对于逆序对问题的抽象:
总应用
- 贪心中的邻项交换排序
例题
- P1774 最接近神的人
考点:归并排序、逆序对
本地代码+题目分析+WA记录 - SWJTU OJ-12.13 F XCPC
考点:归并排序、逆序对(没有相邻元素交换)
题目分析