75. 颜色分类（荷兰国旗问题）

题目解题思路代码

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意: 不能使用代码库中的排序函数来解决这道题。

荷兰国旗包含三种颜色：红、白、蓝。 有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

非进阶思路：

这题我们可以考虑对数组进行两次遍历(使用单指针)。在第一次遍历中，我们将数组中所有的 00 交换到数组的头部（用一个指针pointer来指出头部的范围）。 在第二次遍历中，我们将数组中所有的 11 交换到头部的 00 之后。此时，所有的 22 都出现在数组的尾部，这样我们就完成了排序。

进阶思路： 用双指针

两个指针分别指向 下一个0、2应该存放的位置遇0则交换 当前元素 和 p0空间的值，并 使得 p0指针 指向 下一个0应该存放的位置，遍历下一个元素遇2则交换 当前元素 和 p2空间的值，并 使得 p2指针 指向 下一个2应该存放的位置，遍历下一个元素

代码

非进阶：

class Solution { public void sortColors(int[] nums) { int length=nums.length; int pointer=0;//头部的范围 for (int i = 0; i < length; i++) { if (nums[i]==0){ int temp=nums[pointer]; nums[pointer]=nums[i]; nums[i]=temp; //要注意放入最后一个0了 pointer仍然会加一，所以pointer-1，才是真正的头部范围。 pointer++;//将一个元素放到头部后就要给头部范围加1。 } } for (int i = pointer; i < length; i++) { if (nums[i] == 1) { int temp=nums[pointer]; nums[pointer]=nums[i]; nums[i]=temp; pointer++; } } } }

进阶：

class Solution { public void sortColors(int[] nums) { /** * 双指针 * 两个指针分别指向 下一个0、2应该存放的位置 * 遇0则交换 当前元素 和 p0空间的值，并 使得 p0指针 指向 下一个0应该存放的位置，遍历下一个元素 * 遇2则交换 当前元素 和 p2空间的值，并 使得 p2指针 指向 下一个2应该存放的位置，继续遍历 交换后的当前元素 */ int length=nums.length; int p0=0; int p2=length-1; for (int i=0;i<=p2;i++){//没和p2相遇之前继续循环 if (nums[i]==0){ int temp=nums[p0]; nums[p0]=nums[i]; nums[i]=temp; p0++; } } for (int i=length-1;i>=p0;i--){//没和p0相遇之前继续循环 if (nums[i]==2){ int temp=nums[p2]; nums[p2]=nums[i]; nums[i]=temp; p2--; } } } }