排序问题- 大小为k的n/k个区间

Question

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

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

现在我知道每个区间中最多只有log log k个不同的值，我需要想出一种更快的算法。希望您能帮助我。

谢谢！

- Numerator

---

您目前使用的平衡二叉树方法需要 O(n logloglog(k)) 的时间，因为对于排序二叉搜索树的深度最多为 O(log (log log k))，所以其中一个间隔需要O(k log log log k)的时间。我认为这种方法已经足够快了。此外，您的间隔之间没有任何特定关系，无法将 n * X 降低到 g(n) * X，因此我认为您不能减少 n。 - Saeed Amiri

你说的 n\k 是指 n/k，也就是“n除以k”吗？ - Svante

@Svante：是的，这就是我想说的。 - Numerator

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)。

欢迎提出任何问题，因为我真的很困，不能保证我的思维清晰。

- zw324

Answer 2

你可以在每个区间上使用 计数排序 或 桶排序，每个区间的成本为 O(k)，总成本为 O(n/k * k) = O(n)

然后将每个区间合并在一起，总成本为 O(n)。你的算法将是一个 O(n) + O(n) = O(n) 的算法。

注意：如果你能利用并行性，你可以并行地对所有区间进行排序，总成本为 O(k)。虽然由于合并，你的算法仍然是 O(n)，但它将具有较小的常数因子。

- Aly