---

1）要满足|n1-n2|最小，且|S1-S2|最小，则采用将最小元素都放到S1，最大元素都放到S2，且两个集合相差元素个数不超过

采用快速排序，将集合A按递增次序排序，同时将前n/2个元素视为A1，后n/2个元素视为A2

2）

int partition(int A[], int L, int R) {
    int mid = A[L];
    while (L<R) {
        while (A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while (A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;
    return L;
}

void Qsort(int A[], int L, int R) {
    if (R<=L) retrun;
    int M = partition(A, L, R);
    Qsort(A, L, M-1);
    Qsort(A, M+1, R);
}

int A1[n/2];//保存A1集合元素
int A2[n/2];//保存A2集合元素

void split(int A[], int len) {
    Qsort(A, 0, len-1);
    for (int i=0; i<len/2; i++) {
        A1[i]=A[i];
        A2[i]=A[i+len/2];
    }
}

3）时间复杂度为O(nlogn)，空间复杂度O(logn)