Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.
Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).
Why is Merge Sort better for Linked List?
reference 1 reference 2
如果是直接把链表拿去排序,那么需要O(NlgN)O(NlgN)O(NlgN) 次链表读写,对cache很不友好
如果预先搞个数组,把链表的每个块的起始地址、key存起来,然后去排序,然后使用unording map,那么只需要O(N)O(N)O(N) 的链表读写,其他都是数组读写。 我猜或许性能会好一点
与 图灵班论坛 的连接断开,我们正在尝试重连,请耐心等待