已知由n（n≥2）个正整数构成的集合A={ |0≤ k＜n}，将其划分为两个不相交的子集和，元素个数分别是和，和中元素之和分别为和。设计一个尽可能高效的划分算法，满足最小且最大。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的平均时间复杂度和空间复杂度。
注意：设计一个尽可能高效的划分算法，即设计时间复杂度和空间复杂度较好的算法为优先。
按如下划分，可满足最小且最大
// 测试代码
/*
选择快速排序的算法思想，但不是全排序，只保证枢轴 piovtkey 的左边的数据都比 piovtkey 小，枢轴 piovtkey 的右边的数据都比 piovtkey 大。
比如下方给出的数据里，排序的结果是 2，3，4，5，7，6
此时 piovtkey = 4
*/
#include <iostream>
using namespace std;int main() {// your code goes hereint a[6] = {5, 6, 4, 3, 7, 2};int n = sizeof(a)/sizeof(int);int low = 0, high = n - 1, low0 = 0, high0 = n - 1;int flag = 1, k = n/2;int s1 = 0, s2 = 0;int piovtkey;while(flag){piovtkey = a[low]; // 选择枢轴while(low < high){ // 基于枢轴对数据进行划分while(low < high && a[high] >= piovtkey){--high;}if(low != high){a[low] = a[high];}while(low < high && a[low] <= piovtkey){++low;}if(low != high){a[high] = a[low];}}a[low] = piovtkey;if(low == k - 1){ // 若枢轴是第 n/2 个元素，划分成功flag = 0;}else{if(low < k - 1){low0 = ++low;high = high0;}else{high0 = --high;low = low0;}}}for(int i = 0; i < 6; i++){cout<< a[i] << " ";}cout<<endl;for(int j = 0; j < k; j++) s1 += a[j];for(int q = k; q < n; q++) s2 += a[q];cout<< "sum : "<< s2 - s1 <<endl;;
}
标准答案如下：
https://www.nowcoder.com/questionTerminal/c9950515d3e14b0e998a6b449ecbfeeb?mutiTagIds=597&page=1&onlyReference=false
