(1)算法的基本设计思想(4分)
由题意知，将最小的 $\lfloor n/2 \rfloor$ 个元素放在 $A_1$ 中，其余的元素放在 $A_2$ 中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将 $n$ 个整数划分为两个子集。根据划分后枢轴所处的位置 $i$ 分别处理：
①若 $i = \lfloor n/2 \rfloor$，则分组完成，算法结束；
②若 $i < \lfloor n/2 \rfloor$，则枢轴及之前的所有元素均属于 $A_1$，继续对 $i$ 之后的元素进行划分； 
③若 $i > \lfloor n/2 \rfloor$，则枢轴及之后的所有元素均属于 $A_2$，继续对 $i$ 之前的元素进行划分； 
基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。 

(2) 算法实现 (9 分)

int setPartition(int a[ ], int n)
{
    int pivotkey, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;
    int s1 = 0, s2 = 0;
    
    while(flag)
    {
        pivotkey = a[low];    // 选择枢轴
        
        // 基于枢轴对数据进行划分
        while(low < high)    
        {
            while(low < high && a[high] >= pivotkey)
                --high;
            if(low != high)
                a[low] = a[high];
                
            while(low < high && a[low] <= pivotkey)
                ++low;
            if(low != high)
                a[high] = a[low];
        }  // end of while(low < high)
        
        a[low] = pivotkey;
        
        // 如果枢轴是第n/2小元素，划分成功
        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) 算法的平均时间复杂度和空间复杂度 (2 分)
本参考答案给出的算法平均时间复杂度是 O (n)，空间复杂度是 O (1)。