algorithm - 排序问题 - n/k 间隔，每个间隔大小为 k

Question

给定一个大小为 n 的数组，它被分成 n/k 个间隔，每个间隔大小为 k。每个区间中的值都大于其左侧区间中的值，小于其右侧区间中的值。我想在最短的时间内对这些值进行排序。

我想到的天真的解决方案只是对每个区间中的所有值进行排序，这将“花费”O(k log k)，所有 n 的总成本/k O(n log k) 间隔。我想知道是否有更有效的方法。

现在我知道在每个间隔中我只有 log log k 个不同的值，我需要想出一个更快的算法。我希望得到你的帮助。

谢谢!

Answer 1

这是一个极其丑陋的答案:

1. Take the first interval;
2. Since logK should be small, we allocate logK binary tree nodes, and we place the first element in the middle;
3. For the rest of the elements, we use method similar to binary search to search if it is already included, or we add this element;
4. Produce a sorted list with all the values in the interval;
5. Use Counting Sort with this list on the interval;
6. Do this for all the intervals.

用于 2,3 的时间是 O(K*logloglogK)，因为搜索最多需要 logloglogK(记录 loglogK 元素)并重复 K 次。 4 最多使用 O(loglogK) 时间遍历所有有值的节点。 5 需要 O(K) 时间，类似于计数排序。所以总时间应该是O(nlogloglogK)。

欢迎任何问题，因为我真的很困，不能保证我在思考。