如何递归将百万级排序数组划分为N份直至每份规模≤N？

核心逻辑说明 #

无需修改原数组，仅通过计算索引范围完成递归分区：

• 终止条件：当前分区的元素数量（end - start + 1）≤ 指定的N
• 递归逻辑：将当前分区均等划分为N个子分区，对每个子分区重复执行分区操作
• 结果收集：按递归深度记录所有分区的索引范围

过程式伪代码实现 #

// 主函数：启动分区流程
FUNCTION partition(array, N)
    array_length = LENGTH(array)
    // 存储各深度的分区结果，结构为：深度 -> [分区范围列表]
    result = EMPTY DICTIONARY
    // 初始调用：处理整个数组（索引0到array_length-1），深度0
    CALL partition_recursive(0, array_length - 1, N, 0, result)
    RETURN result
END FUNCTION

// 递归辅助函数：处理单个分区，收集结果
FUNCTION partition_recursive(start, end, N, current_depth, result)
    partition_size = end - start + 1
    // 终止条件：当前分区元素数≤N，直接记录
    IF partition_size ≤ N THEN
        // 如果当前深度未在结果中，先初始化列表
        IF current_depth NOT IN result THEN
            result[current_depth] = EMPTY LIST
        END IF
        // 添加当前分区的索引范围（格式为"start-end"）
        ADD TO result[current_depth] STRING(start) + "-" + STRING(end)
        RETURN
    END IF

    // 记录当前深度的分区（如果是首次进入该深度）
    IF current_depth NOT IN result THEN
        result[current_depth] = EMPTY LIST
    END IF
    ADD TO result[current_depth] STRING(start) + "-" + STRING(end)

    // 计算每个子分区的基础大小，处理无法整除的情况
    sub_partition_base = partition_size // N
    remainder = partition_size % N

    // 遍历划分N个子分区
    current_start = start
    FOR i FROM 0 TO N-1
        // 前remainder个子分区多1个元素，平衡边界
        sub_partition_end = current_start + sub_partition_base - 1
        IF i < remainder THEN
            sub_partition_end = sub_partition_end + 1
        END IF
        // 递归处理子分区，深度+1
        CALL partition_recursive(current_start, sub_partition_end, N, current_depth + 1, result)
        // 更新下一个子分区的起始索引
        current_start = sub_partition_end + 1
    END FOR
END FUNCTION

关键细节说明 #

1. 边界平衡：当数组长度无法被N整除时，前remainder个子分区会多包含1个元素，保证分区尽可能均等
2. 结果结构：用字典按深度分组，方便后续按层级输出嵌套格式
3. 性能优化：仅计算索引不操作原数组，百万级元素处理效率极高，无额外内存开销（除了存储结果的索引字符串）

示例输出格式（以N=2，数组长度8为例） #

深度0: [0-7]
  深度1: [0-3], [4-7]
    深度2: [0-1], [2-3], [4-5], [6-7]

内容的提问来源于stack exchange，提问作者Oh Fiveight