2016·43 集合划分：从全排序到 partition 单侧递归

本文属于「从暴力解到最优解」专题。套路照旧：先把暴力解写对 → 按判分口径估分 → 找浪费 → 升级成最优解。

题目

已知由 n（n ≥ 2）个正整数构成的集合 A = {a_k | 0 ≤ k < n}，将其划分为两个不相交的子集 A₁ 和 A₂，元素个数分别是 n₁ 和 n₂，A₁ 和 A₂ 中元素之和分别为 S₁ 和 S₂。设计一个尽可能高效的划分算法，满足 |n₁ − n₂| 最小且 |S₁ − S₂| 最大。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

题面写了「尽可能高效」——按总纲的分类，暴力解和最优解之间存在真实分差。总分 15 分。

第一步：把暴力解写对

动手之前先把两个条件翻译成人话，这一步本身就是设计思想的得分内容：

• |n₁ − n₂| 最小：两个子集一个装 ⌊n/2⌋ 个、一个装 ⌈n/2⌉ 个，n 为偶数时差 0、奇数时差 1。从任何一边搬一个元素到另一边，个数差只会变大——所以对半分是唯一选择。
• |S₁ − S₂| 最大：个数框死之后，要让和的差距拉到最大，自然是小的归一堆、大的归一堆——A₁ 装最小的那 ⌊n/2⌋ 个，A₂ 装剩下较大的。任何「交换」都会让小堆变大、大堆变小，差就缩了。

两个条件合起来，题目其实在问一件事：把最小的 ⌊n/2⌋ 个元素挑出来。考场上最自然的第一反应：排序。排完序，前一半就是 A₁，后一半就是 A₂：

#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;   // 升序比较器（正整数相减不会溢出）
}

int setDivide(int A[], int n) {
    qsort(A, n, sizeof(int), cmp);              // 全排序：小的自动聚到前面
    int k = n / 2;                              // A[0..k-1] 为 A₁，A[k..n-1] 为 A₂
    int s1 = 0, s2 = 0;
    for (int i = 0; i < k; i++) s1 += A[i];
    for (int i = k; i < n; i++) s2 += A[i];
    return s2 - s1;                             // S₁ ≤ S₂，差本身就是 |S₁ - S₂|
}

拿 {7, 2, 9, 4, 5, 1} 走一遍：排序得 {1, 2, 4, 5, 7, 9}，A₁ = {1, 2, 4}，A₂ = {5, 7, 9}，个数差 0，和差 21 − 7 = 14。手工枚举可以确认没有更好的划分。返回值直接写 s2 - s1 就够了——A₁ 全是较小元素，S₁ ≤ S₂ 恒成立，差本身就是绝对值。

复杂度：排序 $O(n\log n)$，两遍累加 $O(n)$，总时间 $O(n\log n)$；除排序自身的递归栈外没有辅助结构。

它值多少分

408 算法设计题的判分拆成两个维度（详见总纲）：

• 正确性（占大头）：这份解的设计思想完整——不光说了「排序后对半分」，还论证了为什么这样同时满足两个条件（个数严格对半 + 小堆对大堆）；代码逻辑自洽；复杂度照实写 $O(n\log n)$。正确性维度的分都能拿到。
• 最优性（小头）：题目解析明确写着：全排序也得对，但 $O(n\log n)$ 比 partition 法的平均 $O(n)$ 慢一档，不拿满分。最优性那档拿不到。

也就是说这道 15 分的题，暴力解拿正确性分、丢最优性分，主体分在手。复杂度那一问照实写 $O(n\log n)$——分析与算法一致本身是得分点。

暴力解的浪费在哪

用总纲的三个问题审一遍：

有没有干超出需要的活？——有。排序买到的是全序：A₁ 内部谁比谁小、A₂ 内部谁比谁大，排得清清楚楚。但回头看题目要什么——只要一条分界线：最小的 ⌊n/2⌋ 个在左、其余在右，两边内部的顺序毫无用处。花 $O(n\log n)$ 买全序，实际只用了一条分界，这就是浪费。

有没有重复处理已经出结果的部分？——有。换成快排的视角看得更清楚：快排第一轮 partition 结束时，pivot 已经归位，它把数组切成了左右两段——此时你其实已经知道分界线落在哪一段里了。但全排序不管这个，它对两段都继续无差别递归。目标只在一边，另一边的所有后续工作全是白干。

浪费的本质：题目只要「第 ⌊n/2⌋ 小的位置」这一个信息，排序却把 n 个元素的完整次序全算了出来。

智慧化改造：partition 只追着目标那半打

对策是总纲第三问的思路——让手里的工具只干必要的活。快排的 partition 一趟就能做到：任选 pivot（取首元素），一趟扫描把 ≤ pivot 的甩到左边、≥ pivot 的甩到右边，pivot 归位到下标 i。然后看落点：

• i == k − 1（k = ⌊n/2⌋）：pivot 正好是第 k 小，分界成立，收工；
• i < k − 1：左边攒的元素还不够 k 个，去右半段继续 partition；
• i > k − 1：左边攒多了，去左半段继续。

每轮只递归含目标位置的那一半，规模平均砍半：工作量 $n+n/2+n/4+\cdots =2n$，平均 $O(n)$。这就是比全排序快一档的全部秘密——它对「不含答案的那半」一个字都不多碰。

int setDivide(int A[], int n) {
    int low = 0, high = n - 1;
    int k = n / 2;        // 分界后 A[0..k-1] 为 A₁，A[k..n-1] 为 A₂
    int s1 = 0, s2 = 0;

    // partition 找第 k 小（落到下标 k-1 的位置）
    while (low < high) {
        int pivot = A[low];
        int i = low, j = high;
        while (i < j) {
            while (i < j && A[j] >= pivot) j--;
            A[i] = A[j];
            while (i < j && A[i] <= pivot) i++;
            A[j] = A[i];
        }
        A[i] = pivot;                    // pivot 落在 A[i]

        if (i == k - 1) break;           // 落点正好是分界
        else if (i < k - 1) low = i + 1; // 左侧不够，往右半部继续
        else                high = i - 1;
    }

    // 累加 A₁、A₂ 的元素和
    for (int idx = 0; idx < k; idx++) s1 += A[idx];
    for (int idx = k; idx < n; idx++) s2 += A[idx];

    return s2 - s1;          // A₂ 全是大数，S₂ ≥ S₁，直接返 S₂ - S₁
}

从暴力解升级过来时，几个细节决定这份代码是加分还是翻车：

• 内层两个 while 必须带 i < j 守门。某一段元素全部 ≥ pivot（或全部 ≤ pivot）时，缺了守门条件的 j--/i++ 会一路冲出数组边界。
• 等号要留在比较里：A[j] >= pivot、A[i] <= pivot。两边都写成严格不等号，遇到与 pivot 相等的元素会两头僵住，全相同序列直接死循环。
• 只递归一半。写着写着顺手把两侧都递归了，就变回完整快排——排序 $O(n\log n)$ 的老路，优化白做。单侧递归是这个算法的灵魂。
• 落点比较对象是 k − 1。第 k 小的元素落在下标 k − 1，和 k 比就错位一格，划出来的两半个数差变成 2。
• k 取 ⌊n/2⌋。n 为偶数时取哪半无差别；n 为奇数时 A₂ 多拿一个（最大的那批多分给大堆），S₂ − S₁ 只会更大，与题目要求方向一致。

复杂度：时间平均 $O(n)$（每轮缩到一半，等比级数求和 2n）；最坏 $O(n^2)$（每次 pivot 恰是当前段极值，partition 退化成 $n+(n-1)+\cdots$）。空间 $O(1)$，原地 partition，只有 low/high/i/j/pivot 几个标量。第 (3) 问把平均和最坏分开写清楚，这是「分析与算法一致」的完整版。

两版对照跑一遍

同一组输入 [7, 2, 9, 4, 5, 1]（答案 14），先看全排序版——注意 sort 把两半内部也整理得井井有条，而这些顺序后面根本没人用：

加载可视化中...

再看 partition 单侧递归版——每轮 pivot 归位后，只朝含分界的那半继续，另一半再也不碰：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• 全排序后对半分：本文的暴力解。划分结果完全正确，两个条件都达标，拿正确性分；$O(n\log n)$ 够不到平均 $O(n)$，最优性那档拿不到。
• 返回值口径：题面要的是 |S₁ − S₂|。由于 A₁ 全为较小元素，S₁ ≤ S₂ 恒成立，直接返回 S₂ − S₁ 即可；返回 S₁ − S₂ 会得到负数，与题意有出入。
• 最坏情况的表述：答卷主体写平均 $O(n)$ 及其推导（单侧递归 + 等比级数）即可；最坏 $O(n^2)$（pivot 每次都是极值）可以作为补充说明点到，体现你对 partition 行为的完整理解。

下一步

• 在 OJ 上把两版代码都提交跑一遍：ds-2016-43 集合划分
• 回到题库看这道题的完整解析与错因：真题库 · 数据结构

相关真题（1题）

2016Q43综合题15分

去刷题

集合划分算法：将 n 个正整数的集合划分为元素数量差最小、元素之和差最大的两个子集（排序法）

排序通论