tl_xujiayi的博客

博客

2023-05-07 15:50:27 By tl_xujiayi

我们可不可以使用若干个队列存储数列中有序的子序列，然后用线段树维护队首，每次比较队首求最小值，直到所有队列为空。

这种排序算法似乎时间复杂度最好 $O(n)$，最坏 $O(n \log n)$。

lovelove

这不是选择排序的思路吗？

tl_xujiayi

小六蒟蒻，说错轻喷

zexal

问题是你怎么维护有序队列？如果你是一个个存，为什么不用优先队列？

zexal

或者也有可能我理解错了，你也可能是对于每一个数字，都比较队列，找到一个比他大的，然后放进去，不然就新建一个。但是你这种东西不如直接排序啊。

tl_xujiayi

大致流程，例如 3 5 4 6 7 建队过程是 3 直接入 1 号队列 5 比 3 大，直接入 1 号队列 4 比 5 小，入 2 号队列 6 比 4 大，入 2 号队列 7 比 6 大，入 2 号队列

2805734199h

这个是不是用值域线段树维护的啊，如果是值域线段树，那离散化也要先排序

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。