如何在双向链表上做 $O(n\lg n)$ 的原地排序

ppip @ 2022-05-14 21:59:32

by ppip @ 2022-05-14 22:00:56

我的问题啊。快排直接收了吧。

by 山田リョウ @ 2022-05-14 22:06:49

@OneZzz6174 可以做到原地吧

by Echidna @ 2022-05-14 22:06:52

@ppip 显然不行

放到数组上然后快排再给塞回去。

快排要求能够随机访问，像链表这种访问中间某一个数都需要 O(n) 的东西还是算了吧

by 山田リョウ @ 2022-05-14 22:07:55

就是类似普通归并，由于寻找链表中点不影响时间复杂度，直接找就行，而且显而易见两个链表合并可以做到原地

by xfrvq @ 2022-05-14 22:08:49

@Echidna 那 list::sort() 是什么东西啊？

@cxy2022 就是原地，我刚刚搞错了

by Graygoo @ 2022-05-14 22:08:51

归并应该可以吧

by 山田リョウ @ 2022-05-14 22:09:49

@Echidna 不用吧，随机挑一个点作为分割点是 O(n)，再将这些点分开也能原地做到 O(n) 吧

by Echidna @ 2022-05-14 22:12:17

@OneZzz6174 @cxy2022

有道理

所以为什么不直接放到数组上然后 sort 呢

by Graygoo @ 2022-05-14 22:18:52

草

by bh1234666 @ 2022-05-14 22:21:35

@ppip 话说你是咋让你badge里面的&不被转义掉的啊