题目来源于王道论坛 已知由n（n≥2）个正整

解答：

（1）算法的基本设计思想

由题意知，将最小的ën/2)û个元素放在A₁中，其余的元素放在A₂中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理：

①若i=ën/2)û，则分组完成，算法结束；

②若i＜ën/2)û，则枢轴及之前的所有元素均属于A₁，继续对i之后的元素进行划分；

③若i＞ën/2)û，则枢轴及之后的所有元素均属于A₂，继续对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) {
 piovtkey=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=--high;
 low=low0;
 }
 }
 }
 for(i=0;i<k;i++) s1+=a[i];
 for(i=k;i<n;i++) s2+=a[i];
 return s2-s1;
}

【（1）（2）的评分说明】

①本题目只需将最大的一半元素与最小的一半元素分组，不需要对所有元素进行全部排序。参考答案基于快速排序思想，采用非递归的方式实现。若考生设计的算法满足题目的功能要求且正确，则（1）、（2）根据所实现算法的平均时间复杂度给分，细则见下表。

②若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，可参照①的标准给分。

③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。

④参考答案中只给出了使用C语言的版本，使用C++语言的答案视同使用C语言。

（3）算法的平均时间复杂度和空间复杂度

本参考答案给出的算法平均时间复杂度是O(n)，空间复杂度是O(1)。