1 class Solution { 2 public: 3     void sortColors(vector<int>& nums) { 4         if (nums.size() == 0) return; 5         vector<int> start(3, -1); 6         start[nums[0]] = 0; 7         for (int i = 1; i < nums.size(); ++i) { 8             if (nums[i] == nums[i - 1]) continue; 9             else {10                 if (start[nums[i]] == -1) {11                     if (nums[i] == 2) {12                         start[2] = i; continue;13                     }14                     else if (nums[i] == 1) {15                         if (start[2] == -1) {16                             start[1] = i; continue;17                         }18                         else {19                             start[1] = start[2];20                             nums[i] = 2;21                             nums[start[1]] = 1;22                             ++start[2];23                         }24                     }25                     else {26                         // 不可能出现start[1] = start[2] = -1的情况，开始第一个元素已经确定一个27                         // 这里start[1]和start[2]至少有一个不是-128                         if (start[2] != -1) {29                             nums[start[2]] = 0;30                             start[0] = start[2];31                             ++start[2];32                             nums[i] = 2;33                             if (start[1] != -1) {34                                 nums[start[1]] = 0;35                                 nums[start[0]] = 1;36                                 start[0] = start[1];37                                 ++start[1];38                             }39                             else continue;40                         }41                         else {42                             nums[start[1]] = 0;43                             nums[i] = 1;44                             start[0] = start[1];45                             ++start[1];46                         }47                     }48                 }49                 else {50                     if (nums[i] == nums[i - 1]) continue;51                     else {52                         if (nums[i] == 0) {53                             if (start[2] == -1) {54                                 nums[i] = 1;55                                 nums[start[1]] = 0;56                                 ++start[1];57                             }58                             else {59                                 nums[start[2]] = 0;60                                 nums[i] = 2;61                                 ++start[2];62                                 if (start[1] != -1) {63                                     nums[start[1]] = 0;64                                     nums[start[2] - 1] = 1;65                                     ++start[1];66                                 }67                             }68                         }69                         else {70                             // nums[i] == 1, 不可能为2，且前一个一定是271                             nums[i] = 2;72                             nums[start[2]] = 1;73                             ++start[2];74                         }75                     }76                 }77             }78         }79     }80 };

 1 class Solution { 2     public: 3         void sortColors(vector<int>& A) { 4             int red = 0, blue = A.size() - 1; 5             for (int i = 0; i < blue + 1; ) { 6                 if (A[i] == 0) swap(A[i ++], A[red ++]); 7                 else if (A[i] == 2) swap(A[i ++], A[blue --]); 8                 else ++ i; 9             }10         }11 };