我们可不可以使用若干个队列存储数列中有序的子序列，然后用线段树维护队首，每次比较队首求最小值，直到所有队列为空。
这种排序算法似乎时间复杂度最好 $O(n)$，最坏 $O(n \log n)$。
tl_xujiayi的博客
博客
关于一种新型排序思想
2023-05-07 15:50:27 By tl_xujiayi
评论
lovelove
这不是选择排序的思路吗？
- 2023-05-09 12:33:26
tl_xujiayi
小六蒟蒻，说错轻喷
- 2023-05-09 20:01:52
zexal
问题是你怎么维护有序队列？如果你是一个个存，为什么不用优先队列？
- 2023-05-10 20:04:59
zexal
或者也有可能我理解错了，你也可能是对于每一个数字，都比较队列，找到一个比他大的，然后放进去，不然就新建一个。但是你这种东西不如直接排序啊。
- 2023-05-10 20:06:30
tl_xujiayi
大致流程，例如 3 5 4 6 7 建队过程是
3 直接入 1 号队列
5 比 3 大，直接入 1 号队列
4 比 5 小，入 2 号队列
6 比 4 大，入 2 号队列
7 比 6 大，入 2 号队列
- 2023-05-10 20:22:10
2805734199h
这个是不是用值域线段树维护的啊，如果是值域线段树，那离散化也要先排序
- 2023-05-31 09:44:23
发表评论
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。
- Universal Online Judge |
鄂公网安备 42010202000505 号 |- 鄂ICP备 14016048 号
Server time: 2024-11-21 14:29:08