计算机学科专业基础2016 真题档案

（1）算法基本设计思想
要使两个子集元素个数差最小且和的差最大，应将最小的⌊n/2⌋个元素放入A₁，其余放入A₂。采用快速排序中的划分思想，基于枢轴进行划分，通过非递归方式逐步将数组划分为两部分，使得左半部分恰好包含最小的⌊n/2⌋个元素，右半部分包含剩余元素。最后分别计算两部分的和并返回其差值。

（2）算法描述（C语言）

int setPartition(int a[], int n) {
    int pivokey = 0, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;
    int s1 = 0, s2 = 0;
    while(flag) {
        pivokey = a[low]; // 选择枢纽
        while(low < high) {
            while(low < high && a[high] >= pivokey) --high;
            if(low != high) a[low] = a[high]; // 替换较大的数
            while(low < high && a[low] <= pivokey) ++low;
            if(low != high) a[high] = a[low]; // 替换较小的数
        }
        a[low] = pivokey; // 完成交换枢纽
        if(low == k - 1) {
            flag = 0;
        } else {
            if(low < k - 1) {
                low0 = ++low;
                high = high0;
            } else {
                high0 = --high;
                low = low0;
            }
        }
    }
    for(i = 0; i < k; i++) s1 += a[i];
    for(i = k; i < n; i++) s2 += a[i];
    return s2 - s1;
}

（3）时间复杂度与空间复杂度

• 平均时间复杂度：O(n)，期望线性时间完成划分。
• 空间复杂度：O(1)，仅使用常数额外空间。