P1177 【模板】快速排序

P1177 【模板】快速排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

1.注意i ++ j -- 因为还要继续往下走

2.第k小就用这个写（虽然也能stl nth_element(,,,) )

3.左排右排递归

4.为什么mid = (l + r) / 2; a[i] < a[mid] 不行？？？

#include 
using namespace std;
int n;
int a[100010];
void quick_sort(int l, int r){
    int mid = a[(l + r) / 2];
    int i = l, j = r;
    do{
        while(a[i] < mid) i ++;
        while(a[j] > mid) j --;

        if(i <= j){
            swap(a[i], a[j]);
            //继续往下走
            i ++;
            j --;
        }
    }while(i <= j);
    if(i < r) quick_sort(i, r);
    if(l < j) quick_sort(l, j);
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    quick_sort(0, n - 1);
    for(int i = 0; i < n; i ++) cout << a[i] << " ";
    return 0;
}