![[数据结构]算法设计题--划分子集(快速排序思想)](/uploads/reation/bcimg2.png)
[数据结构]算法设计题--划分子集(快速排序思想)
问题已知由n个正整数构成的集合A={ak}(0<=k<n)，将其划分为两个不相交的子集A1和A2，元素个数为n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|s1-s2|最大。要求：给出算法的基本设计思想。分析算法的时间复杂度和空间复杂度。解答算法思想将最小的[n/2]个元素放在A1中，其余的元素放在A2中，划分满足要求。不需要对全部元素进行排序，可以仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。然后将划
