AcWing 785. 快速排序
原题链接
简单
作者:
二十二桥枫别雨
,
2022-07-04 10:41:22
,
所有人可见
,
阅读 121
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6+10;
int n;
int q[N];
void quick_sort(int q[] , int l ,int r) {
//传入的数据不规范
if ( l >= r) return ;
//因为下面先do,再进行判断,所以这里i从l前一个走,j从r后一个走,x为这个区间的中位数,也就是快排中的枢轴
int i = l - 1 , j = r+1 , x = q[l + r >> 1];
while(i < j) {
do i++ ; while(q[i] < x);//左边找一个大于枢轴的数
do j-- ; while(q[j] > x);//右边找一个小于枢轴的数
if(i < j) swap(q[i],q[j]);//范围合理,交换两者
}
quick_sort(q , l , j );//对枢轴左边进行操作
quick_sort(q , j+1 , r);//对枢轴右边进行操作
}
int main() {
cin>>n;
for(int i = 0 ; i < n ; i++) {
cin>>q[i];
}
quick_sort(q , 0 , n - 1);
for(int i = 0 ; i <n ;i++)
{
cout<<q[i]<<" ";
}
return 0;
}