[【C++算法】43.分治_快排_颜色分类(过渡)

---

题目链接：

75. 颜色分类

---

题目描述：

---

解法

分治：就是分而治之

这题作为过渡，不使用分治。

解法：三指针

---

C++ 算法代码：

class Solution 
{public:void sortColors(vector<int>& nums) {int n = nums.size();// 初始化指针：// left 指向最后一个已知的 0 的下一个位置// right 指向第一个已知的 2 的前一个位置// i 是当前遍历的索引int left = -1, right = n, i = 0;while(i < right) // 当 i 小于 right 时继续遍历{// 如果当前元素是 0，将其与 left 指针指向的元素交换// 然后移动 left 和 i 指针if(nums[i] == 0) swap(nums[++left], nums[i++]);// 如果当前元素是 1，不需要交换，只需移动 i 指针else if(nums[i] == 1) i++;// 如果当前元素是 2，将其与 right 指针指向的元素交换// 然后移动 right 指针，但 i 指针不移动，因为交换过来的元素需要重新检查else swap(nums[--right], nums[i]);}}
};