AcWing 785. 快速排序
原题链接
简单
作者:
qing123
,
2021-01-23 20:28:18
,
所有人可见
,
阅读 260
题目描述
边界条件很重要 ,注意不要死循环
样例
#include<iostream>
using namespace std;
const int N =1e5+10;
int q[N];//存储数据的数组
//快速排序算法
void quick_sort(int q[],int l,int r)
{
if(l>=r) return ;//检测边界是否争取,区间长度大于1
int i=l-1,j=r+1,x=q[l+r+1>>1];//取中间位置
while(i<j){
do i++; while (q[i]<x);//小于参考轴,继续移动
do j--; while(q[j]>x);//当右边指针大于轴时,向左移动
if(i<j) swap(q[i],q[j]);//当i,j未相交执行到这里,表示都指向了
//待交互的数
}
//j的右边是拍好的
quick_sort(q,l,i-1);
quick_sort(q,i,r);
}
int main()
{
int n;
scanf("%d",&n);//输入数组长度
for(int i=0;i<n;i++)scanf("%d",&q[i]);//输入待排序数据
quick_sort(q,0,n-1);//调用排序
for(int i=0;i<n;i++)printf("%d ",q[i]);
return 0;
}