51Nod--1018 排序

青旅半醒 2022-06-14 01:56 173阅读 0赞

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1018][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1018]

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题

给出N个整数，对着N个整数进行排序  
Input  
第1行：整数的数量N（1 <= N <= 50000)  
第2 - N + 1行：待排序的整数（-10^9 <= A\[i\] <= 10^9）  
Output  
共n行，按照递增序输出排序好的数据。  
Input示例  
5  
5  
4  
3  
2  
1  
Output示例  
1  
2  
3  
4  
5

使用时间复杂度为O(n\*logn) 的排序就行了，快排、归并排序、堆排序，这里用快排，也可以直接使用C++ STL 的 sort 函数模板，代码：

#include <iostream>
    #include <stdio.h>
    using namespace std;
    const int N = 50010;
    int a[N];
    
    void quickSort(int a[], int start, int end) {
        int i = start, j = end, t = a[start];
        if(start >= end) {
            return ;
        }
        while(i < j) {
            while(i < j && a[j] >= t) {
                j--;
            }
            swap(a[j], a[i]);
            while(i < j && a[i] <= t) {
                i++;
            }
            swap(a[i], a[j]);
        }
        quickSort(a, start, i-1);
        quickSort(a, i+1, end);
    }
    
    int main() {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            scanf("%d", a+i);
        }
    
        quickSort(a, 0, n-1);
    
        for(int i = 0; i < n; i++) {
            printf("%d\n", a[i]);
        }
    
        return 0;
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1018]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1018

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 51Nod 1432 独木舟

[1432 独木舟][1432] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 10 [难度：2级算法题][2] ![star.pn

落日映苍穹つ/ 2022年09月27日 00:27/ 0 赞/ 141 阅读

相关 51nod 1067 博弈

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

比眉伴天荒/ 2022年08月21日 12:59/ 0 赞/ 198 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 200 阅读

相关 51nod1432 贪心

上船问题。排序之后枚举最大重量就可以了。 include <map> include <queue> include <sta

谁践踏了优雅/ 2022年07月29日 08:58/ 0 赞/ 174 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 210 阅读

相关 51Nod--1018 排序

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1018][http_www.51nod

青旅半醒/ 2022年06月14日 01:56/ 0 赞/ 174 阅读

相关 51nod 1287 加农炮

[1287 加农炮][1287] ![ok.png][] 题目来源： [Codility][] 基准时间限制：1 秒空间限制：131072 KB 分值: 40 [难度：4

雨点打透心脏的1/2处/ 2022年06月09日 11:17/ 0 赞/ 191 阅读

相关 51nod-1770

为该问题添加一个话题隐藏话题 [1770 数数字][1770] 基准时间限制：1 秒空间限制：262144 KB 分值: 20 [难度：3级算法题][3] ![s

小灰灰/ 2022年05月28日 12:51/ 0 赞/ 182 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 189 阅读

相关逆序数（51Nod1019）(归并排序)

[1019 逆序数][1019] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：基础题][Link 1] ![star.png][] 收藏 ![

以你之姓@/ 2022年05月24日 00:10/ 0 赞/ 208 阅读