已知由n（M>2）个正整数构成的集合A={a<k<n},将其划分为两个不相交的子集A1 和A2，元素个数分别是n1和n2，A1和A2中的元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|s1-s2|最大。要求：
1） 给出算法的基本设计思想。
2） 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3） 说明你所设计算法的平均时间复杂度和空间复杂度。
// 方法一;对整个数组进行排序，然后再将整个数组等分为两份,此时因为利用的是选择排序，所以时间复杂度为O (n^2)
int setpartition(int[] a, int n)
{
Selectsort(a, 0, n - 1);
int s1 = 0, s2 = 0; //S1,S2表示数组的前半部分和后半部分之和
for (int i = 0; i < n / 2; i++)
s1 += a[i];
for (int i = n / 2; i < n; i++)
s2 += a[i];
return s2 - s1;
}
void Selectsort(int[] a, int n)
{ //对长度为n的数组a进行选择排序
for (int i - 0; i < n - 1; i++)
{
int min = i; //表示本轮次排序中的最小值所在的数组下标
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[min])
min = j;
}
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
算法的基本设计思想
-
由题意知，将最小的 n/2 （向下取整） 个元素放在A1中，其余的元素在A2中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理:
- 若i= n/2 （向下取整） ，则分组完成，算法结束;
- 若i< n/2 （向下取整） ，则枢轴及之前的所有元素均属于 A1，继续对 i之后的元素进行划分
- 若i> n/2 （向下取整） ，则枢轴及之后的所有元素均属于 A2，继续对 i之前的元素进行划分
基于该设计思想实现的算法，无须对全部元素进行全排序，其平均时间复杂度是 O(n) 空间复杂度是 0(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]; //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;
}
}
