主页
Featured image of post ACM学习笔记——排序……

ACM学习笔记——排序……

基础算法——排序算法……

文章字数:532
预计阅读时长: 分钟

该笔记还未完成整理,待日后继续整理……

该笔记目前直接复制的之前的笔记,还未调整格式。页面格式、内容、链接等可能存在混乱错误……

排序

不考虑算法

  • 选择排序、冒泡排序、插入排序 \(O(n^2)\)
  • 计数排序、基数排序、桶排序 \(O(n+w)\)
  • 希尔排序、锦标赛排序

快速排序

应用

  • 寻找第k大的数

归并排序

应用

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

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


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

    • 模板题:
      P1908 逆序对

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

总应用

  • 贪心中的邻项交换排序

例题