首页 > 代码库 > 洛谷 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 【模板】快速排序