标题408数据结构–2016年统考真题（C语言）

一、题目描述

已知由n(n>=2)个正整数构成的集合A={a_k|0<=k<n},将其划分为两个不相交的子集A₁和A₂,元素个数分别是n1和n2，A₁和A₂中的元素之和分别为S₁和S₂。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：

1. 给出算法的基本设计思想。
2. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释
3. 说明你所设计的算法的平均时间复杂度和空间复杂度。

二、解决思路

1. 暴力法–排序
直接采用时间复杂度较好的排序算法，比如快速排序，排序之后根据数组元素个数划分，若数组元素个数为奇数，则S₂集合比S₁多划分一个数据元素，此时|n1-n2|=1；若数组元素个数为偶数，则S₂集合和S₁数据元素个数相同为数组元素个数的一半，此时|n1-n2|=0.该方法的时间复杂度为：O(nlog₂n)、空间复杂度为O(1).
2.枢轴划分法
由题意知，将最小的n/2（向下取整）个元素放在A₁中，其余的元素放在A₂中，分组的结果即可满足题目要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理：
① 若i=n/2(向下取整)，则分组结束，算法结束
② 若i<n/2(向下取整)，则枢轴及之前的所有元素均属于A₁，继续对i之后的元素进行划分。
③ 若i>n/2(向下取整)，则枢轴及之后的所有元素均属于A₂，继续对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];
		}
		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(int i=0;i<k;i++){
		s1+=a[i];
	}
	for(int i=k;i<n;i++){
		s2+=a[i];
	}
	return s2-s1;
}