第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
基础练习 数列排序
资源限制
内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200
输入格式
第一行为一个整数n。
第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。
输出格式
输出一行，按从小到大的顺序输出排序后的数列。
样例输入
5
8 3 6 4 9
样例输出
3 4 6 8 9
题目解析
本题目很明显说的是给定一个长度n的数列，我们可以理解成数组或者列表，只需要从小到大排列即可，由于C语言没有提供排序的函数，故而需要自己写，那么其它的三种语言都是提供了自然排序的函数，我们直接使用就可以，还是非常方便的。
C语言
C语言这里用的是快排，可以看到QuickSort函数，快拍的写法还是很直接的，但是这个毕竟是有一个递归，其实所有的递归都不是那么好理解的，我们最开始比赛也不建议纯搞C语言，这样会在编码的时候浪费很多时间，一般算法比赛考的都是思维，如果把精力都放在编码上就会浪费很多时间，得不偿失。
#include <stdio.h> #include <stdlib.h> void Print(int *data,int n) { int i; for(i=0;i<n;i++) { printf("%d ",data[i]); } printf("\n"); } int Split(int *data,int pre,int rear) { int value=data[pre]; while(pre<rear) { while(data[rear]>=value && pre<rear) rear--; data[pre]=data[rear]; while(data[pre]<value && pre<rear) pre++; data[rear]=data[pre]; } data[pre]=value; return pre; } //快速排序 void QuickSort(int *data,int pre,int rear) { if(pre<rear) { int mid=Split(data,pre,rear); QuickSort(data,pre,mid-1); QuickSort(data,mid+1,rear); } } int main() { int i; int n; int *data; scanf("%d",&n); data=(int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) { scanf("%d",&data[i]); } QuickSort(data,0,n-1); Print(data,n); return 0; }
我们写了这么多代码总得看看效果把，我们就提交一下看看啊。
C++语言
#include<iostream> #include<algorithm> using namespace std; int cmp(int a,int b) { return a<b; } int main() { int n; while(cin>>n) { int a[205]; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n,cmp); cout<<a[0]; for(int i=1;i<n;i++) { cout<<' '<<a[i]; } cout<<endl; } return 0; }
Java语言
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.valueOf(br.readLine()); int[] arr = new int[n]; String[] s = br.readLine().split(" "); for(int i=0; i< n; i++) { arr[i] = Integer.parseInt(s[i]); } Arrays.sort(arr); for(int i=0; i< arr.length; i++) { System.out.print(arr[i]+" "); } } }
Python语言
n = int(input()) a = list(map(int,input().split())) a.sort() for i in a: print(i,end = ' ')
我们来看看Python语言的效果：这里我用的是蓝桥杯的计分，这里没有对应的内存消耗，其实看看内存还有时间是非常好的。
其实在这里看，Python的效果还是不错的，起码内存才是C语言的4倍，比想想中要节约一些，时间上也是慢一些优先，所以很多的程序还是使用C语言更快的，我们用Python只是方便于编码来解决问题而已。
总结
四种语言其实解题代码量我们可以清晰的看到，本次我们参加的依然是java组，但是慢慢的算法可能真的会向Python方向进军，因为基础算法大家也都会，我们在很多基础的函数上进行快速操作可以节约很多的时间，从而给自己更多的思考时间，我觉得是非常美妙的事情。
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
