问题是：在 O(n)O(n) 的时间复杂度，O(1)O(1) 的空间复杂度内将只含有0，1，2三种数的数组排序
时间复杂度 O(nlong(n))O(nlong(n))
空间复杂度 O(1)O(1)
#include <iostream>

using namespace std ;

const int N = 100010 ;

int a[N] ;
int n ;

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


int main(){
    scanf("%d",&n) ;

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]) ;
    }
    int l=0,r=n-1 ;

    quick_sort(a,0,n-1) ;

    for(int i=0;i<n;i++){
        printf("%d ",a[i]) ;
    }
    return 0 ;
}
彩虹快速排序（即数组中只有k种数） 一开始想用二分的，时间复杂度超了，也记录一下，当作笔记
时间复杂度 O(nlong(k))O(nlong(k))
空间复杂度 O(1)O(1)
#include <iostream>

using namespace std ;

const int N = 100010 ;

int a[N] ;

void quick_sort(int a[],int l,int r,int from,int to){
    if(l>=r || from == to){//当数组中只有一种颜色时或左边界超过右边界时返回
        return ;
    }
    int x = (from+to)/2,i=l,j=r ;
    while(i<j){
        while(i<j && a[i]<=x){
            i++ ;
        }
        while(i<j && a[j]>x){
            j-- ;
        }
        if(i<j){
            swap(a[i],a[j]) ;
            i++ ;
            j-- ;
        }
    }
    quick_sort(a,l,j,from,x) ;
    quick_sort(a,j+1,r,x+1,to) ;
}

int main(){
    int n ;
    scanf("%d",&n) ;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]) ;
    }
    quick_sort(a,0,n-1,0,3) ;
    for(int i=0;i<n;i++){
        printf("%d ",a[i]) ;
    }
    return 0 ;
}
荷兰国旗问题
正确解法: 思路也是分治，将数组中大于分割值的数放右边，小于的放左边，等于的放中间

时间复杂度 O(n)O(n)
空间复杂度 O(1)O(1)
void quick_sort(int a[],int l,int r){
    int i = l-1 ;//左边界
    int j = r+1 ;//右边界
    while(l<j){
        if(a[l]<1){
            swap(a[++i],a[l++]) ;
        }else if(a[l]>1){
            swap(a[l],a[--j]) ;
        }else{
            l++ ;
        }
    }
}