leetcode75. 颜色分类

分析

选择o(1)的空间复杂度排序即可。

class Solution {
public:
    void quick_sort(vector<int>&nums,int l,int r){
        if(l>=r)return ;
        int i=l-1,j=r+1,x=nums[(l+r)>>1];
        while(i<j){
            do i++;while(nums[i]<x);
            do j--;while(nums[j]>x);
            if(i<j)swap(nums[i],nums[j]);
        }
        quick_sort(nums,l,j),quick_sort(nums,j+1,r);
    }
    void sortColors(vector<int>& nums) {
        quick_sort(nums,0,nums.size()-1);
    }
};