1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| const int Maxn=1e6+5;
void quick_sort(int a[],int l,int r) { if(l>=r) return ; std::swap(a[l+rand()%(r-l+1)],a[l]); int base = a[l]; int i=l+1,j=l+1,k=r; while(i<=k) { if(a[i]<base) std::swap(a[i++],a[j++]); else if(a[i]>base) std::swap(a[i],a[k--]); else i++; } std::swap(a[j-1],a[l]); quick_sort(a,l,j-2); quick_sort(a,k+1,r); } int main() { srand(time(0)); int n; int arr[Maxn]; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",arr+i); quick_sort(arr,0,n-1); for(int i=0;i<n;i++) printf("%d ", arr[i]); }
|