AcWing 算法基础课. 快速排序
原题链接
简单
作者:
叱咤月海鱼鱼猫
,
2023-10-31 19:56:32
,
所有人可见
,
阅读 77
快速排序
#include <iostream>
using namespace std;
const int N = 100010 ;
/* 快排思想:
* 根据分界点:将小于分界点放在左区域,大于分界点的放在右区域
* 分界点取中间时,区域用(l,j),(j+1,r)和(l,i-1),(i,r)都可以
* 分界点取arr[l]时,不能用i;分界点取arr[r]时,不能用j,否则会越界
* 会一种即可,取中间值通用性更强*/
void quick_sort(int *arr,int l , int r){
if(l >= r) return;
int x = arr[(l+r) >> 1 ]; // 取中间值
int i = l-1 , j = r + 1;
while(i < j){
do i++ ; while (arr[i] < x); // 找到比分界点大的值
do j-- ; while (arr[j] > x) ;
if(i < j) swap(arr[i],arr[j]) ;
else break ;
}
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
int main(){
/*优化数据IO*/
ios::sync_with_stdio(false) ;
cin.tie(nullptr);cout.tie(nullptr);
int n ;
int arr[N] ;
cin >> n ;
for(int i = 0 ; i < n ; i++) cin >> arr[i] ;
quick_sort(arr,0,n-1) ;
for(int i = 0 ; i < n ; i++) cout << arr[i] << " " ;
cout << endl ;
return 0 ;
}