方法一、直接采用插入排排序或快速排序即可。
代码如下：
插入排序
class Solution { public: //插入排序 void sortColors(vector<int>& nums) { for(int i = 1; i < nums.size(); i++){ int temp = nums[i]; //从第二个元素开始 int j = i - 1; while(j >= 0 && nums[j] > temp){ //将data[j]后移 nums[j+1] = nums[j]; //j的位置前移 j--; } nums[j+1] = temp; //将temp插入正确位置 } } };快速排序
class Solution { public: void sortColors(vector<int>& nums) { int i = 0; int j = nums.size() - 1; return quickSort(i, j, nums); } void quickSort(int left, int right, vector<int>& arr){ if(left >= right) return ; int i = left, j = right, temp; int flag = arr[left]; //取第一个数作为标记位 while(i < j){ while(i < j && arr[j] >= flag) //先从右向左找小于flag的数，等待交换 j--; while(i < j && arr[i] <= flag) //再从左向右找大于flag的数，等待交换 i++; //交换小于flag和大于flag的数 if(i < j){ temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //标记数归位 arr[left] = arr[i]; arr[i] = flag; quickSort(left, i - 1, arr); //递归左边 quickSort(i + 1, right, arr);//递归右边 } };方法二、因为有很多重复数字，所以快排不是最优解，且会遍历多次数组。那如何对数组一次扫描即可？采用三路快排，0都放在左边，2都放在右边，1直接跳过。
维护三个指针，一个0指针一个2指针一个当前指针，从头到尾的遍历；如果当前是0，和0指针的下一个元素交换；如果当前是2和2指针的前一个元素交换。需要注意的是，和2的前一个元素交换后当前当前指针留在原地，因为交换过来的元素还不确定到底是0还是1、2代码如下：
class Solution { public: void sortColors(vector<int>& nums) { int p0 = 0; //0指针 int p2 = nums.size() - 1; //2指针 for(int i = 0; i <= p2; ){ //i代表当前指针 if(nums[i] == 0) swap(nums[i++], nums[p0++]); else if(nums[i] == 2) swap(nums[i], nums[p2--]); else i++; } return ; } };