题目描述

• key取a[l+r>>1]

• 严格小于、大于

C++ 代码

#include<iostream>

using namespace std;

int n;
int a[100003];

void Qsort(int l,int r){
    if(l>=r) return;

    int key=a[l+r>>1];

    int i=l-1,j=r+1;
    while(i<j){
        do i++;while(a[i]<key);
        do j--;while(a[j]>key);
        if(i<j) swap(a[i],a[j]);
    }
    Qsort(l,j);
    Qsort(j+1,r);
}


int main(){

    cin>>n;
    for(int i=0;i<n;++i){
        scanf("%d",&a[i]);
    }

    Qsort(0,n-1);

    for(int i=0;i<n;++i){
        printf("%d ",a[i]);
    }

    return 0;
}