这次分享来源于群友分享头条面试经历，其中有一题内容是关于快速排序的灵活运用，快排边界问题有点烦 水个博客

谢谢 @猛虎嗅蔷薇 同学

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

先上y总快速排序模板

时间复杂度 $ O(nlong(n)) $
空间复杂度 $ 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(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(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++ ;
        }
    }
}