首页 > 代码库 > 洛谷 1177 【模板】快速排序
洛谷 1177 【模板】快速排序
题目描述
利用快速排序算法将读入的N个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料,掌握后独立完成。(C++选手请不要试图使用STL,虽然你可以使用sort一遍过,但是你并没有掌握快速排序算法的精髓。)
输入输出格式
输入格式:
输入文件sort.in的第1行为一个正整数N,第2行包含N个空格隔开的正整数a[i],为你需要进行排序的数,数据保证了A[i]不超过1000000000。
输出格式:
输出文件sort.out将给定的N个数从小到大输出,数之间空格隔开,行末换行且无空格。
输入输出样例
输入样例#1:
54 2 4 5 1
输出样例#1:
1 2 4 4 5
说明
对于20%的数据,有N≤1000;
对于100%的数据,有N≤100000。
#include<cstdio>using namespace std;int i[100001],n;void Qsort(int t1,int t2){ int x=t1,y=t2,m=i[(t1+t2)>>1],t; do { while (i[x]<m) x++; while (i[y]>m) y--; if (x<=y) { t=i[x]; i[x]=i[y]; i[y]=t; x++; y--; } } while (x<=y); if (t1<y) Qsort(t1,y); if (x<t2) Qsort(x,t2);}int main(){ scanf("%d",&n); for(int a=1;a<=n;a++) scanf("%d",&i[a]); Qsort(1,n); for(int a=1;a<=n;a++)
if(a==1) printf("%d",i[a]); else printf(" %d",i[a]); printf("\n"); return 0;}
洛谷 1177 【模板】快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。