确定性划分集合为指定大小子集的更优复杂度方案咨询

结论是不存在严格优于「先排序再划分」的通用实现方案，原因如下：

• 需求的核心约束是「划分结果和输入顺序无关、输出序列固定、每个子集元素不超过k个」，这要求你必须基于元素本身的固有属性，给所有元素建立一个全局唯一的确定顺序，才能保证同一个元素不管输入顺序如何，都会被分到固定的子集里，同时保证子集大小均匀不超限。
• 对于基于比较的通用算法场景，给n个唯一元素建立全序的理论复杂度下界是Ω(n log n)，和常规排序算法的时间复杂度完全一致，没有优化空间。
• 如果你尝试不用全排序的方案，比如用快速选择逐次找第k、2k…大的元素作为分界，当k远小于n时，总时间复杂度会达到O(n²/k)，反而比排序的O(n log n)性能更差；如果用哈希做分桶，又无法确定性保证每个桶的元素数量不超过k的限制，不满足需求。
• 针对题目中元素为正整数的场景，你可以用基数排序、计数排序这类非比较排序算法把排序过程的复杂度降到O(n)，但这本质上还是「先排序再划分」的思路优化，不属于脱离排序的更优方案。

内容的提问来源于stack exchange，提问作者Mike Graham