一、题目(leetcode75 颜色分类 --三分数组)
二、思路
算法核心：三指针分治策略
该问题被称为“荷兰国旗问题”（Dutch National Flag Problem），由计算机科学家Edsger Dijkstra提出。其核心思想是通过三个指针将数组划分为三个区域，逐步将元素归位。
指针定义与规则
1. 指针分工
left：标记`0`的右边界（初始指向头部）
i：当前遍历位置（初始指向头部）
right：标记`2`的左边界（初始指向尾部）
2. 遍历规则
三、代码
class Solution {
public:void sortColors(vector<int>& nums) {int left=-1,right=nums.size(),i=0;while(i<right){if(nums[i]==0)swap(nums[++left],nums[i++]);else if(nums[i]==1)++i;elseswap(nums[i],nums[--right]);}}
};复杂度与适用场景
时间复杂度：O(n)，线性遍历。
空间复杂度：O(1)，仅使用常数指针。
适用场景：元素种类有限（如3种）的快速原地排序，例如图像处理中的像素值排序、分类统计等。
总结
三指针法通过巧妙的分区策略，将荷兰国旗问题的时间复杂度优化到极致。该算法不仅是一道经典面试题，更体现了分治思想在实际工程中的应用价值。掌握这一方法，可轻松应对类似的多分类排序问题。