关于sort和快速排序

小叶枫ovo @ 2022-08-27 18:44:22

by StarLbright40 @ 2022-08-27 19:06:24

这题的正解复杂度应该是 O(n)。

从 C++11 开始 sort 使用内省排序，是严格 O(n\log n) 的。

by __er @ 2022-08-27 19:15:46

我跟不上了啊，在我心中sort还是时常O(n^2)的，现在发现这些东西还得好好学

by 小叶枫ovo @ 2022-08-27 19:59:51

雀食，正解是分治O（n）求第k小数，但直接快排+快读排好序再输出第k项也能过，而sort+快排则不行

by 小叶枫ovo @ 2022-08-27 20:02:33

@小叶枫ovo 打错了是sort+快读

by 小叶枫ovo @ 2022-08-27 20:11:46

bdfs了下发现sort好像比快排还快。。疑惑这点（蒟蒻嘤嘤嘤）