题目描述
利用快速排序算法将读入的 N 个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）
输入格式
第 1 行为一个正整数 NN，第 2 行包含 N 个空格隔开的正整数 ai，为你需要进行排序的数，数据保证了 Ai 不超过 10^9 。
输出格式
将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
输入 #1复制
1. 5 2. 4 2 4 5 1
输出 #1复制
1 2 4 4 5
说明/提示
对于 20% 的数据，有 N≤103；
对于 100% 的数据，有 N≤10^5。
#include<iostream> using namespace std; int a[100000]; void yyds(int n,int q)//2分法 就是不断的把比中间的数小的放在左边，大的放在右边，重复这个过程。 { int i=n,j=q; int mid=a[(n+q)/2]; while(i<=j)//如果刚刚好到达中间的数就退出循环 { while(a[i]<mid) i++;//找到左边比中间大的数 while(a[j]>mid) j--;//找到右边比中间小的数 if(i<=j)//可能会出现都到达中间位置 { swap(a[i],a[j]); i++; j--; } } if(n<j)yyds(n,j);//因为j在左边i在右边 if(i<q)yyds(i,q); } int main() { int i,m; cin>>m; for(i=1;i<=m;i++) { cin>>a[i]; } yyds(1,m); for(i=1;i<=m;i++) { cout<<a[i]<<' '; } }
