algorithm - 将列表分层到无序分区

我正在努力为以下问题找到一个好的算法：
输入：n个整数的未排序列表
输出：p大小（大致）相等的未排序列表，其中每个列表的最小元素都大于其前面列表的最大元素
目标是对输出进行分层，以便在p=3的情况下，我得到3个小、中、大数字的无序列表（按顺序）。
例如：
n=10，p=3
输入：[4，1，8，7，9，3，6，0，2，5]
输出：[1，0，2]，[4，3，6，5]，[8，7，9]]
显然，我可以在O(n*log(n))时间内通过简单的排序和分区来完成这项工作，但我想知道这是否不能在线性时间内完成我知道quickselect在预期的O(n)平均情况下运行，所以我的直觉是这个问题应该在O(p*n)时间内解决。
天真地说，我认为您可以简单地运行quickselect p次，依次查找下一个第k个最小的元素，然后对每个元素执行类似基数的排序，以便根据在原始步骤中标识的p轴来划分元素。
所以：
我不确定我概述的算法是否有效
我不确定
确实需要O(p*n)
即使是O(p*n)，我也不确定
这是一个最优的复杂度（虽然我怀疑是这样的，因为它）
似乎在p=1和p=n的边缘情况下有效）
不是很好
优雅的
有更好的算法吗？
谢谢

最佳答案

quickselect实际上是一个分区算法，因此在quickselect之后不需要额外的步骤。
假设我们有一个函数分区（arr，lo，hi），它返回一些k，然后重新排列lo <= k < hi，如果arr则返回arr[i] <= arr[k]，如果i < k则返回arr[k] <= arr[i]那么，实际上，QuickSelect是：

# After this call:
#   arr[i] <= arr[med] if lo <= i < med
#   arr[med] <= arr[i] if med < i < hi
QuickSelect(arr, lo, med, hi):
  if lo < hi:
    k = Partition(arr, lo, hi)
    if med < k:
      QuickSelect(arr, lo, med, k)
    else if k < med:
      QuickSelect(arr, k + 1, med, hi)

这与快速排序非常相似：

QuickSort(arr, lo, hi):
  if lo < hi:
    k = Partition(arr, lo, hi)
    QuickSort(arr, lo, k)
    QuickSort(arr, k + 1, hi)

由于quickselect在指定点对数组进行分区（这比查找相关元素稍微多一些），因此我们可以很容易地将stratify定义为对quickselect的重复调用：

Stratify(arr, n, p):
  for i from 0 to p - 2 (inclusive):
    QuickSelect(arr, floor(i * n / p), floor((i+1) * n /p, n)

由于quickselect是k < i，所以上面的分层是O(n)。如果O(p*n)不在O(n log n)中，则仅对数组排序的选项将采用p，因此上述分层非常有用（由于O(log n)是一个很小的数字，因此在实践中很可能是排序更优的情况。）
然而，很容易将分层合并到quickselect中，这是一种我们可以称之为quickstratify的算法。QuickStratify执行快速排序，精确到阵列固定的位置：
为了方便起见，一种报告给定索引属于哪个层的函数：

Stratum(i, n, p): floor(i * p / n)

现在：

QuickStratify(arr, n, p, lo, hi):
  if Stratum(lo, n, p) < Stratum(hi, n, p):
    k = Partition(arr, lo, hi)
    QuickStratify(arr, n, p, lo, k)
    QuickStratify(arr, n, p, k + 1, hi)

我很确定quickstratify是平均时间log n，但我没有现成的证据，可能我错了。