题意

给定数字数组,按其升序或降序输出

方法

排序并输出

我们先将输入保存在vector中

根据要求的升序或降序进行排序

最后输出数组的内容

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        vector<int>a;
        for(int i = 0;i<n;i++){ // 读入数组
            int v;
            scanf("%d",&v);
            a.push_back(v);
        }
        int o;
        scanf("%d",&o);
        if(o == 0){ // 升序
            sort(a.begin(),a.end());
        }else{ // 降序
            sort(a.begin(),a.end(),greater<int>());
        }
        for(auto w:a){ // 输出
            printf("%d ",w);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 读入输出的时间复杂度为$O(n)O(n)$,排序的时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$, 所以总时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

空间复杂度: 主要的空间消耗在存储数组,所以空间复杂度为$O(n)O(n)$

改变输出不改变排序

以样例1 2 4 9 3 55 64 25为例

我们对其排序后得到的数组为1 2 3 4 9 25 55 64

注意到其 升序反过来就是降序

所以我们可以直接按照升序排序,控制输出的遍历方向即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        vector<int>a;
        for(int i = 0;i<n;i++){
            int v;
            scanf("%d",&v);
            a.push_back(v);
        }
        sort(a.begin(),a.end()); // 升序排序
        int o;
        scanf("%d",&o);
        if(o == 0){
            for(auto w:a){ // 升序
                printf("%d ",w);
            }
        }else{
            for(int i = a.size()-1;i>=0;i--){ // 降序 控制 遍历方向即可
                printf("%d ",a[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 读入输出的时间复杂度为$O(n)O(n)$,排序的时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$, 所以总时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

空间复杂度: 主要的空间消耗在存储数组,所以空间复杂度为$O(n)O(n)$