785. 快速排序

785. 快速排序 

来自 <https://www.acwing.com/problem/content/submission/code_detail/18083617/> 


#include<iostream>
using namespace std;
const int N=100010;
int a[N];

// 快排属于分治算法（板子）
void quick_sort(int a[],int l,int r){
  if(l>=r){
    return ;
  }
  int i=l-1,j=r+1;
  int mid=a[(l+r)/2];
  while(i<j){
    do{
      i++;
    }while(a[i]<mid);
    do{
      j--;
    }while(a[j]>mid);
    if(i<j){
      swap(a[i],a[j]);
    }
    
  }
  quick_sort(a,l,j);
  quick_sort(a,j+1,r);
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  quick_sort(a,0,n-1);
   for(int i=0;i<n;i++){
    cout<<a[i]<<" ";
  }
  return 0;
}