已知由n(n≥2)个正整数构成的集合A={ak } 0≤k<n}， 将其划分为两个不相交的子集A1 和A2 ， 元素个数分别是n1和n2 ， A1和A2中元素之和分别为S1和S2 。 设计一个尽可能高效的划分算法， 满足|n1 -n2 |最小且|S1 -S2 |最大。 要求：
给出算法的基本设计思想。
算法的基本设计思想
由题意知，将最小的 [n / 2]个元素放在 A1中，其余的元素放在 A2中，分组结果即可满 足题目要求。仿照快速排序的思想，基于枢轴将 n 个整数划分为两个子集。根据划分后枢轴 所处的位置 i 分别处理：
①若 i= [n / 2]，则分组完成，算法结束;
②若 i＜ [n / 2]，则枢轴及之前的所有元素均属于 A1，继续对 i 之后的元素进行划分；
③若 i＞ [n / 2] ，则枢轴及之后的所有元素均属于 A2，继续对 i 之前的元素进行划分；
基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是 O(n)， 空间复杂度是 O(1)。
根据设计思想， 采用C或C++语言描述算法， 关键之处给出注释。
算法实现
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];
returns2-s1;
}
说明你所设计算法的平均时间复杂度和空间复杂度。
算法平均时间复杂度是 O(n)，空间复杂度是 O(1)。