请注意，这道题中的所有快速排序题解的时间复杂度复杂度均是错误的

P1923 【深基9.例4】求第 k 小的数

Autre @ 2023-11-15 14:34:03

在每轮递归中，按照某种确定性方案选出一个元素作为基准元素，这样的算法的时间复杂度为 O(n^2)，只有随机选取一个元素才能让其复杂度降至期望 O(n\log n)，最劣 O(n^2)。

by No21 @ 2023-11-15 14:51:34

@zhaohanwen spfa？？？

by Little_Cart @ 2023-11-15 14:52:14

@No21 我的意思就是我记得是有快排的，但是确实卡了（）

by 初星逝者 @ 2023-11-15 14:53:23

@No21

https://www.cnblogs.com/curo0119/p/8638603.html

heap排序在平均时间复杂度是O(nlgn)，最坏情况也是O(nlgn)，看起来要比快排要快。

bdfs

by zhaohanwen @ 2023-11-15 14:53:42

@No21 @Little_Cart 看一下第一篇题解，至少将近 4 年前过不去。

by Autre @ 2023-11-15 14:54:45

@zhaohanwen SPFA 啥时候成随机化算法了/jy

by Little_Cart @ 2023-11-15 14:55:19

@Castilian 确实，不一直是 O(nm) 的吗（）（）（）（）

by zhaohanwen @ 2023-11-15 14:55:29

@Castilian 您是不是误解了我的意思。。。

by Little_Cart @ 2023-11-15 14:56:22

@zhaohanwen 快排卡 sort 没问题，但是 sort 永远是 O(n \log n) 级别的好吧

by No21 @ 2023-11-15 14:56:53

@zhaohanwen 测评环境问题吧，几年前那个速度，5e6 带只 log 几年前还是比较费劲的，但是现在没什么问题

by zhaohanwen @ 2023-11-15 14:56:58

@Little_Cart 为啥我查到的是 O(kn)，最劣 O(nm)啊。~~我也忘了啥时候知道的。~~