读题

中心思想：依题意，仅需将序列分成两部分，前[n / 2]个元素为左序列，其他元素为右序列，利用快排思想，循环递归至左序列元素均不大于右序列即为所求，左右序列内部均无须排序。
※按标准答案全序列排序非最佳答案，至少扣2分。

闫式快排法写法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, q[N], sum1, sum2;

void quick_sort(int l, int r)
{
    if(l == r) return;
    int x = q[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++ ; while(q[i] < x);
        do j -- ; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    if(j > n / 2 - 1) return quick_sort(l, j);
    else if(j < n / 2 - 1) return quick_sort(j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);

    quick_sort(0, n - 1);

    if(!(n % 2)) printf("0 ");
    else printf("1 ");

    for (int i = 0 ; i < n; i ++ )
        if(i < n / 2) sum1 += q[i];
        else sum2 += q[i];
    printf("%d", sum2 - sum1);
    return 0;
}

还是要学学答案，因为上面这总写法不仅拿不了满分还可能多扣分，因为在八股文里面改卷老师不一定认可sort()库函数，如果你执意要写的话，我的建议是把sort（）在试卷上默写出来，就算默写出来也是O(nlogn)也拿不了满分。

(2)算法实现(9分)
int setPartition(int a[ ]，int n)
{ 
    int pivotkey,low=0,low0=0,high=n-l,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 = --m high;
                low = low0;
            }
        }
    }
    for(i = 0;i < k;i ++)  s1 += a[i];
    for(i = k;i < n;i ++)  s2 += a[i];
    return s2 - s1;
}

//八股文快排写法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, q[N], sum1, sum2;

void quick_sort(int l, int r)
{
    if(l == r) return;
    int i = l, j = r;
    int t = q[i];
    while(i < j)
    {
        while(i < j && q[j] >= q[i]) j--;
        if(i != j) q[i] = q[j];
        while(i < j && q[i] <= t) i ++;
        if(i != j) q[j] = q[i];
    }
    q[i] = t;
    if(i == n / 2 - 1) return;
    else if(i < n / 2 - 1) return quick_sort(++ i, r);
    else if(i > n / 2 - 1) return quick_sort(l, -- j);
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);

    quick_sort(0, n - 1);

    if(!(n % 2)) printf("0 ");
    else printf("1 ");

    for (int i = 0 ; i < n; i ++ )
        if(i < n / 2) sum1 += q[i];
        else sum2 += q[i];

    printf("%d", sum2 - sum1);
    return 0;
}

来看看评分说明：

这个博客，后面还会继续更新增加新的题型

如果你排序掌握的不牢固，看看这个大佬：
https://www.acwing.com/file_system/file/content/whole/index/content/1505927/