AcWing 785. 快速排序
原题链接
简单
作者:
TheWitcher
,
2021-02-09 20:09:16
,
所有人可见
,
阅读 342
快速排序
如果quick_sort(arr, l, i - 1);
quick_sort(arr, i, r);
必须 x = arr[(l + r + 1) >>1];
因为当区间长度为2时,如果x = arr[(l + r) >> 1];会gg
#include<iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N];
void quick_sort(int arr[], int l, int r){
if(l >= r) return;
int i = l - 1, j = r + 1, x = arr[(l + 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]);
}
quick_sort(arr, l, j);
quick_sort(arr, j + 1, r);
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
for(int i = 0; i < n; i++)
printf("%d ", a[i]);
}
----------
作者:TheWitcher
链接:https://www.acwing.com/file_system/file/content/whole/index/content/1663588/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
字好看%%%
ipad太难写了
T-T
是的!玻璃上打滑\\感觉没有完美的解决方案