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

【正确答案】算法实现 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; if(low==k-1) //如果枢轴是第n/2小元素，划分成功 flag=0: else //否则继续划分 {if(low＜k-1) {low0=++low; high=high0; } else { high0=--m high; low=low0; } } } for(i=0; i＜k; i++)s1+=a[i]; for(i=k; i＜n; i++)s2+=a[i]; return s2-s1; }

【正确答案】算法的平均时间复杂度和空间复杂度 本参考答案给出的算法平均时间复杂度是O(n)，空间复杂度是O(l)。