将一组数字分成$ k $排序组

Question

我有这个第一个任务：
您有一组数字 $ s={\ dots \} $ 长度 $ n $ 。
和一个数字 $ k $ 。

两个 $ n $ 和 $ k $ 是 $ 2的权力$ 和： $ 1

您的任务是编写一种算法（伪代码），该算法（伪代码）拆分 $ s $ 进入 $ k $ SAME（每个具有相同的长度）： $ s_1，s_2，\ dots，s_k $ ，使得 $ S_I $ 小于 $ s_ {i + 1} $ 的所有数字，因为所有 $ 1 \ Leq i \ Leq K-1 $ 时间复杂性 $ o（n \ cdot k）$ （任务结束1）

第二个（另一个问题，但与第一个问题）的任务是相同的，但建议更快的算法 - psuedo-code（时间复杂性）

例如：

对于 $ s={11,5,2,7,1,13,15,16 \} $ 和 $ k= 4 $ 我会返回（向左）：
$ \ {16,15 \}，\ {13,11 \}，\ {5,7 \}，\ {1,2 \} $
注意这些组内的数字的顺序不必处于任何特定的顺序。

我的去：
我没有尝试过什么..上帝：

1. 我想做一个桶排序。

2. 也许选择一个随机的枢轴并做一个为每个组选择。< / p>

3. make $ k $ 空组长度 $ \ frac {n} $ 每个（“提前”），然后选择 $ k $ -th每个迭代的更小的元素。

4. make $ k $ 空组长度 $ \ frac {n} $ “提前”，然后将每个数字放在第一个，一旦我们遇到更大的数字，我们将最小的数字移动到上面的示例（下面的明确细节）：

这是我到目前为止的算法（第4号）：

首先，我们有一个空 $ k= 4 $ 长度 $ \ frac {n} {k}=frac {8} {4}= 2 $ 然后 $ 11 $ ，然后 $ 5 $ ：
$ \ {11,5 \}，\ {，\}，\ {，\}，\ {，\} $ 然后 $ 2 $ 来电，但它小于 $ 5 $ 或 $ 11 $ so $ \ {11,5 \}，\ {2，\}，\ {，\}，\ {，\} $ 然后 7美元$ ，它大于 $ 5 $ 所以它替换它并移动 $ 5 $ 到下一个集：
$ \ {11,7 \}，\ {2,5 \}，\ {，\}，\ {，\} $ 等...

它应该工作，但我不确定什么是运行的复杂性。对于每个集合（ $ k $ 时间）我必须运行 $ \ frac {n} {k} $ 迭代（每个子集的长度）

如果我理解正确，没有什么工作。这里没有什么可以给我时间复杂性 $ o（n \ cdot k）$ ...
我甚至没有开始考虑第二种解决方案..因为我无法通过第一个。

我会很感激你的帮助！

Answer 1

你的第二个想法似乎很接近。这是实际的算法（不需要随机枢轴）：

1. 查找 $ i {n \ over k} $ 'thounting 每个 $ 1 \ le i \ le K $ 。这将需要 $ o（n）$ 每次 $ k $ 值： $ O（nk）$ 。
2. 对于每个这样的 $ i $ ，将所有元素放在 $ i {n over k} $之间'th和 $（i + 1）{n \ over k} $ 'thous统计 $ i $ 'th桶。对于每个 $ i $ 它会花费 $ o（n）$ 并且有 $ k $ $ i $ 的不同值，因此总计 $ o（nk ）$ 。

两个步骤占用 $ o（nk）$ ，因此整个算法在 $ o（nk）$ < / span>如需要

提示第二个问题：思考如何将该算法与Quickssort的粗版本相结合