小叶枫ovo @ 2022-08-27 18:44:22
它们的时间复杂度不都是O（nlogn）级吗？但此题qsort可过，而sort需O2，不开O2会卡2个点。求解。
by AllureLove2410 @ 2022-08-27 18:46:06
这道题要用分治吧
sort快过快排，因为sort并不全是快排
by JRzyh @ 2022-08-27 18:46:54
因为这题按理说O（nlogn）过不了
by __er @ 2022-08-27 18:48:07
试试引入随机化
by __er @ 2022-08-27 18:48:46
sort容易退化成
by Xiiii @ 2022-08-27 18:51:55
qsort在这道题主要是二分，所以第k小的数在前一半内的话后面一半就直接抛弃了 sort是要把所有数据都排序 所以理论上这道题的qsort用时约为sort一半 （不是很懂 猜测）
by Xiiii @ 2022-08-27 18:53:02
如果快排先把所有数据都先排序好然后输出a[k]可能就超时了（和我一样）
by XeCtera @ 2022-08-27 18:53:43
@__er sort不会退化
by hereiszd @ 2022-08-27 18:54:36
sort 会退化，但是不容易退化。
by XeCtera @ 2022-08-27 19:04:31
@determinational_zd 内部实现不是有堆排序防退化吗/yiw
by ZVitality @ 2022-08-27 19:05:59
用分治复杂度为