假设给定一个由n个元素组成的序列进行排序由n=k个子序列组成，每个子序列包含k个元素。给定中的元素子序列都小于后续子序列中的元素，并且大于前一个子序列中的元素。
那么，有没有一种O(nlogk(方法可以将无序阵列放入上述阵列中？thx！
问题的不同表述
这个问题可以这样想。你有n个不同大小的球。您希望将这些球组织成n/k个桶，以便每个桶正好包含k个球。此外，这些桶被放置在一条线上，其中最左边的桶包含k个最小的球。左边的第二个桶包含接下来的k个球，如果我们移除最左边的桶，这些球将是最小的。最右边的桶包含k个最大的球。
但在每个桶里你都没有订单。如果你想要最大的球，你知道你必须开始在哪个桶里搜索，但你仍然需要在里面四处搜索。
我将使用术语bucket而不是subsequence，因为subsequence让我思考排序哪个不重要，重要的是归属，所以bucket对我来说更容易。
具有所提出的想象解决方案复杂性的问题
你说k是每个桶的长度(或大小(。因此，它自然可以在1和n之间。
然后询问是否存在可以以这种方式组织元素的O(n log k(解决方案。当我们考虑两个极端k=1和k=n时，你提出的复杂性有一个问题很容易看出。
k=n。这意味着我们只有一个大水桶。这是微不足道的，因为不需要任何操作。但是当k=n时，你提出的复杂性是O(n-logk(=O(n-log n(。
让我们也考虑k=1，因为它有一个类似但相反的问题。
k=1.每个桶包含一个球，我们需要n个桶。这与要求我们对整个序列进行完全排序相同，该序列最多为O(n-logn(。但是你提出的复杂度是O(n log k(=O(n log1(=0(n*0(=0。记住日志1=0。你提出的复杂性似乎根本不适合这个问题。
我们可以在这里停下来说。不，你不能在O(n log k(上随心所欲，因为当你减少bucket的数量时，问题会变得更难，这是没有意义的。更重要的是，随着存储桶数量的增加，它不会变得更容易。
如果我的任务是手动进行排序，我会说将其排序到一个桶中是微不足道的。两个很容易。三个比两个更难。如果你有n个水桶，那就太难了！
更改复杂性的答案然而，如果我们修复您提出的复杂性，那么我们会问以下问题，那么考虑一下会发生什么是很有趣的。有没有一种方法可以在O(n log b(中对这些桶进行排序，其中b是桶的数量(b=n/k(？
这里的极端情况似乎是有道理的。
b=1。一个铲斗。无需排序。O(n log b(=O(n log1(=O。(从技术上讲，这可能仍然是O(1((
b=n。n个桶。需要完全排序。O(n log b(=O(n logn(。
因此，一个解决方案似乎是可能的。但现在这已经超出了问题的范围。然而，我怀疑选择算法和快速选择是可行的。