快排

代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int s[N];

void quickSort(int l, int r){
    if(l >= r) return;
    
    int mid = s[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        do ++i; while(s[i] < mid);
        do --j; while(s[j] > mid);
        if(i < j) swap(s[i], s[j]);
    }
    quickSort(l, j);
    quickSort(j + 1, r);
}

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

Q&A

1. 为什么是 do ++i; while(s[i] < mid);而不是while(s[i] < mid) ++i;

考虑这样一个情况

68 68 68

当队列所有值都相同时，i和j就会停止移动，陷入死循环