由于 |n1−n2|≥0 恒成立，要使得 |n1−n2| 最小，所以

• 当 n 为偶数时， |n1−n2| 最小值为 0 。
• 当 n 为奇数时， |n1−n2| 最小值为 1 。

又要求 |S1−S2| 最大，所有数均为正数，假设 S1≤S2 ，有

• 当 n 为偶数时， S1 为较小的 n/2 个数的和， S2 为较大的 n/2 个数的和。
• 当 n 为奇数时， S1 为较小的 ⌊n/2⌋ 个数的和， S2 为较大的 ⌈n/2⌉ 个数的和。

综上， S1 为较小的 ⌊n/2⌋ 个数的和， S2 为较大的 ⌈n/2⌉ 个数的和。

方法一：快速排序

既然如此，如何获得较小的 ⌊n/2⌋ 个数呢，我们很容易想到将 n 个数进行排序，S1 为前的 ⌊n/2⌋ 个数的和， S2 为后的 ⌈n/2⌉ 个数的和。

通常情况下我们采用快速排序处理排序问题。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}

void randomized_quicksort(int *a, int p, int r) {
    if (p < r) {
        int q = randomized_partition(a, p, r);
        randomized_quicksort(a, p, q - 1);
        randomized_quicksort(a, q + 1, r);
    }
}

int maxDifference(int *a, int n) {
    randomized_partition(a, 0, n - 1);
    int s1 = 0;
    for (int i = 0; i < n / 2; ++i) {
        s1 += a[i];
    }
    int s2 = 0;
    for (int i = n / 2; i < n; ++i) {
        s2 += a[i];
    }
    return s2 - s1;
}

int main(int argc, const char * argv[]) {
    int a[5] = {30, 41, 9, 2, 17};
    int res = maxDifference(a, 5);
    printf("%d", res);
    return 0;
}

复杂度分析：

• 时间复杂度： O(nlog⁡n) 。
• 空间复杂度： O(log⁡n) ，平均情况下递归栈深度为 O(log⁡n) 。

方法二：选择算法

基于比较的排序算法的运行时间下界为 Ω(nlog⁡n) ，那么有没有更优秀的算法处理这个问题呢？答案是有，其实我们并不需要对数组进行完全排序，我们只需要利用快速排序的划分数组算法将数组划分为小于枢轴的部分和大于枢轴的部分，即选择算法。对比快速排序算法和选择算法，快速排序算法需要对所有分支进行递归，选择算法仅需要对包含目标元素的分支进行递归。

通常采用随机化选择算法RANDOMIZED-SELECT。

递归版

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}

void randomized_select(int *a, int p, int r, int i) {
    if (p == r) {
        return;
    }
    int q = randomized_partition(a, p, r);
    int k = q - p + 1;
    if (i == k) {
        return;
    } else if (i < k) {
        randomized_select(a, p, q - 1, i);
    } else {
        randomized_select(a, q + 1, r, i - k);
    }
}

int maxDifference(int *a, int n) {
    randomized_select(a, 0, n - 1, n / 2);
    int s1 = 0;
    for (int i = 0; i < n / 2; ++i) {
        s1 += a[i];
    }
    int s2 = 0;
    for (int i = n / 2; i < n; ++i) {
        s2 += a[i];
    }
    return s2 - s1;
}

int main(int argc, const char * argv[]) {
    int a[5] = {30, 41, 9, 2, 17};
    int res = maxDifference(a, 5);
    printf("%d", res);
    return 0;
}

复杂度分析：

• 时间复杂度： O(n) 。
• 空间复杂度： O(log⁡n) ，平均情况下递归栈深度为 O(log⁡n) 。

迭代版

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}

void randomized_select(int *a, int p, int r, int i) {
    int q, k;
    while (1) {
        q = partition(a, p, r);
        k = q - p + 1;
        if (i == k) {
            return;
        } else if (i < k) {
            r = q - 1;
        } else {
            p = q + 1;
            i = i - k;
        }
    }
}

int maxDifference(int *a, int n) {
    randomized_select(a, 0, n - 1, n / 2);
    int s1 = 0;
    for (int i = 0; i < n / 2; ++i) {
        s1 += a[i];
    }
    int s2 = 0;
    for (int i = n / 2; i < n; ++i) {
        s2 += a[i];
    }
    return s2 - s1;
}

int main(int argc, const char * argv[]) {
    int a[5] = {30, 41, 9, 2, 17};
    int res = maxDifference(a, 5);
    printf("%d", res);
    return 0;
}

复杂度分析：

• 时间复杂度： O(n) 。
• 空间复杂度： O(1) ，使用了常数个辅助变量。