https://www.acwing.com/problem/content/787/
快排 双向指针
- #include<bits/stdc++.h>
- using namespace std;
- const int N=100000;
- int n;
- int q[N];
- void quick_sort(int q[],int l,int r) {
- if(l>=r) return ;
- int x=q[l],i=l-1,j=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() {
- 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;
- }
来源: http://www.bubuko.com/infodetail-3259168.html