【模板】快速排序

题目

利用快速排序算法将读入的 NN 个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第1行为一个正整数N，第2行包含N个空格隔开的正整数ai，为你需要进行排序的数，数据保证了Ai不超过10^9。

输出格式

将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

Sample Input

5
4 2 4 5 1

Sample Output

1 2 4 4 5

数据范围

对于20%的数据，有n<=10^3；
对于100%的数据，有N<=10^5。

---

日常橙题WA了2次的那种
可以使用sort，但为了找虐自我锻炼，我还是手写快排
40分*2
快排讲解：
运用递归思想，把一个未排序的区间选定中值，小的放左，大的放右，并对两部分再次递归求解，时间复杂度平均O(nlogn)，最坏（完全有序）O(n^2)（拒绝卡点，从我做起）

code:

#include<iostream>
//#include<algorithm>
using namespace std;
int n,a[100001];
void srt(int l,int r)
{int mid=a[(l+r)/2],i=l,j=r;while(i<=j){while(a[i]<mid)i++;while(a[j]>mid)j--;if(i<=j)//违反顺序{swap(a[i],a[j]);//交换i++;j--;}}if(l<j)srt(l,j);//快排左边if(i<r)srt(i,r);//快排右边
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];srt(1,n);//快排//sort(a+1,a+n+1);for(int i=1;i<=n;i++)cout<<a[i]<<' ';return 0;
}