我的问题啊。快排直接收了吧。
by ppip @ 2022-05-14 22:00:56
@[OneZzz6174](/user/368107) 可以做到原地吧
by YamadaRyou @ 2022-05-14 22:06:49
@[ppip](/user/374433) 显然不行
放到数组上然后快排再给塞回去。
快排要求能够随机访问，像链表这种访问中间某一个数都需要 $O(n)$ 的东西还是算了吧
by Echidna @ 2022-05-14 22:06:52
就是类似普通归并，由于寻找链表中点不影响时间复杂度，直接找就行，而且显而易见两个链表合并可以做到原地
by YamadaRyou @ 2022-05-14 22:07:55
@[Echidna](/user/82284) 那 `list::sort()` 是什么东西啊？
@[cxy2022](/user/203008) 就是原地，我刚刚搞错了
by xfrvq @ 2022-05-14 22:08:49
归并应该可以吧
by Graygoo @ 2022-05-14 22:08:51
@[Echidna](/user/82284) 不用吧，随机挑一个点作为分割点是 $O(n)$，再将这些点分开也能原地做到 $O(n)$ 吧
by YamadaRyou @ 2022-05-14 22:09:49
@[OneZzz6174](/user/368107) @[cxy2022](/user/203008)
有道理
所以为什么不直接放到数组上然后 sort 呢
by Echidna @ 2022-05-14 22:12:17
草
by Graygoo @ 2022-05-14 22:18:52
@[ppip](/user/374433) 话说你是咋让你badge里面的&不被转义掉的啊
by bh1234666 @ 2022-05-14 22:21:35