排序

不考虑算法

• 选择排序、冒泡排序、插入排序 $O(n^2)$
• 计数排序、基数排序、桶排序 $O(n+w)$

  计数排序

• 希尔排序、锦标赛排序

快速排序

应用

• 寻找第k大的数

归并排序

应用

• 寻找逆序对
  可见之前笔记。
  （有关逆序对的问题还可以用树状数组或线段树来解决。）
  • 对于逆序对问题的抽象：
    1. 询问最少经过几次（可能为相邻元素交换）交换，可使数列有序。

    如果限制了为相邻元素交换，最开始很容易想到采用冒泡排序来做，但这样$O(n^2)$很容易TLE……
    发现即便是相邻交换，也是因为存在了逆序对才交换的……
    而每次交换后，能且仅能消除一个逆序对……
    要使序列达到最终有序，则肯定需要消除全部逆序对……
    故此类题目仍为求逆序对，且答案就为逆序对个数……

    ---

    如果没有限制相邻元素交换，那么处理一位数，就能消除这位数的所有逆序对个数（与相邻交换的区别）
    所以就变成了找存在逆序对的位（简称：逆位）的个数。

  • 模板题：
    P1908 逆序对

    本地代码+题目分析+归并排序讲解+WA记录

总应用

• 贪心中的邻项交换排序

例题

• P1774 最接近神的人

  考点：归并排序、逆序对
  本地代码+题目分析+WA记录

• SWJTU OJ-12.13 F XCPC

  考点：归并排序、逆序对（没有相邻元素交换）
  题目分析