专栏首页指点的专栏51Nod--1018 排序

51Nod--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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • L3-004. 肿瘤诊断

    在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

    指点
  • L2-024. 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    指点
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • BZOJ 4289: PA2012 Tax(最短路)

    Description 给出一个N个点M条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点1到点N的最小代价。起点的代价是离开起...

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • Java经典编程50题(面试笔试机试)

    https://blog.csdn.net/alias_fa/article/details/52985112

    林万程

扫码关注云+社区

领取腾讯云代金券