题目的主要信息：

• 输入整型数组和排序标识，对其元素按照升序或降序进行排序

方法一：重载sort函数

具体做法：

可以准备两个重载比较的函数，根据输入的排序标识flag来决定sort函数调用哪一个重载函数。

输入后调用sort函数排序即可。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp0(const int& a, const int& b){ //升序
    return a < b; 
}

bool cmp1(const int& a, const int& b){ //降序
    return a > b; 
}


int main(){
    int n;
    while(cin >> n){
        int flag;
        vector<int> arr(n);
        for(int i = 0; i < n; i++) //输入数组
            cin >> arr[i];
        cin >> flag; //输入排序方式
        if(flag) //根据flag选择排序重载函数
            sort(arr.begin(), arr.end(), cmp1);
        else
            sort(arr.begin(), arr.end(), cmp0);
        for(int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort函数使用快排原理，复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：归并排序

具体做法：

归并排序利用了分治的思想来对序列进行排序。对一个长为$nn$的待排序的序列，我们将其分解成两个长度为$n\mathrm{/}2n/2$的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

如图所示，升序排序每次选取两个子序列的较小值，降序排序则相反选取较大值即可。

#include<iostream>
#include<vector>
using namespace std;

vector<int> temp;
void mergeSort(vector<int>& arr, int l, int r, int flag) {
    if (l >= r)
        return;
    int mid = (l + r) / 2; //中间划分
    mergeSort(arr, l, mid, flag); //排序两边
    mergeSort(arr, mid + 1, r, flag);
    int i = l, j = mid + 1;
    int cnt = 0;
    //合并
    if(flag == 0){ //升序
        while (i <= mid && j <= r) { //依次比较，先取较小值
            if (arr[i] <= arr[j])
                temp[cnt++] = arr[i++];
            else
                temp[cnt++] = arr[j++];
        }
    }else{ //降序
        while (i <= mid && j <= r) { //依次比较，先取较大值
            if (arr[i] >= arr[j])
                temp[cnt++] = arr[i++];
            else
                temp[cnt++] = arr[j++];
        }
    }
    while (i <= mid)  //剩余的元素
        temp[cnt++] = arr[i++];
    while (j <= r)
        temp[cnt++] = arr[j++];
    for (int i = 0; i < r - l + 1; ++i)
        arr[i + l] = temp[i];
}

int main(){
    int n;
    while(cin >> n){
        int flag;
        vector<int> arr(n);
        for(int i = 0; i < n; i++) //输入数组
            cin >> arr[i];
        cin >> flag; //输入排序方式
        temp.resize(arr.size(), 0);
        mergeSort(arr, 0, arr.size() - 1, flag);
        for(int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\; \_2n)$，递归公式为$T(n)=2T(n\mathrm{/}2)+O(n)T(n)=2T(n/2)+O(n)$，故复杂度为$O(nlo{g}_{2}n)O(nlog\; \_2n)$
• 空间复杂度：$O(n)O(n)$，借助了辅助数组temp