两趟扫描,由于排序变量的特殊性，使用计数排序方法可以明显降低至O(n)time O(n) space

关于计数排序：

class Solution {public:    void sortColors(vector
     
      & nums) {        if(nums.size()==0) return;        int len=nums.size();        vector
      
        arr(3,0);        for(int num:nums)            arr[num]++;        int index=0;        for(int i=0;i
      
     

 使用3个变量一趟扫描O(1) space O(n) time

/**使用3个变量来分别表示3个颜色；**/class Solution {public:    void sortColors(vector
     
      & nums) {        if(nums.size()==0) return;        int len=nums.size();        int L=0,M=0,H=len-1;        while(M<=H){            if(nums[M]==1){                M++;continue;            }            if(M<=H&&nums[M]==0){                swap(nums[M],nums[L]);                L++;M++;            }            if(M<=H&&nums[M]==2){                swap(nums[M],nums[H]);                H--;            }        }    }};
     

 具体实现过程参见：