# 75-Sort-Colors

[原题链接](https://leetcode-cn.com/problems/sort-colors/)

## 0x1 题目详情

> 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。

**测试用例:**

> 示例: 输入: \[2,0,2,1,1,0] 输出: \[0,0,1,1,2,2]

## 0x2 解题思路

这道题呢，就是荷兰国旗问题，参考快速排序的partition过程。快速排序就是多次partition，荷兰国旗就是一次partition。比快排简单多了。

这个partition如果非要给他分个类呢，应该是算作三指针的应用。

首先将数组划分为三个区域：

* 小于1的区域
* 等于1的区域
* 大于1的区域

我们可以使用left指针指向小于区域的下一个位置，用right指针指向right区域的上一个位置。用index指针来遍历数组，当index>right，这就表示我们把数组元素都处理完了。

使用多指针的核心步骤是什么？考虑在什么情况下移动指针，以及需要定义一个标准来完成上述的移动操作。

* 如果nums\[index]<1，那么就可以和小于区域的下一个元素交换，这里交换的过来的元素，要么是nums\[index]本身，要么是和nums\[index]相等的元素，**index和left之间不可能出现比nums\[index]小的数**。交换完成后，移动指针，left++，index++
* 如果nums\[index]==1,直接移动index
* 如果nums\[index]>1,需要和大于区域的上一个元素交换，并且right--,为什么不移动index指针呢？因为交换过来的元素我们还没有查看过。

## 0x3 代码实现

```java
class Solution {
    public void sortColors(int[] nums) {
        //很简单的一次partition操作
        int index=0;
        int left=0;
        int right=nums.length-1;
        while(index<=right){
            if(nums[index]==1){
                index++;
            }
            else if(nums[index]<1){
                int temp=nums[left];
                nums[left]=nums[index];
                nums[index]=temp;
                left++;
                index++;
            }
            else{
                int temp=nums[right];
                nums[right]=nums[index];
                nums[index]=temp;
                right--;
            }
        }
        return;
    }
}
```

## 0x4 课后总结

荷兰国旗问题就是快速排序的子集。荷兰国旗已经每次比较的标准确定好了，而快排在每次partition时都需要随机指定标准。(上述所谓的标准就是荷兰国旗中的数字1)。

最后不建议将赋值语句插入其他语句，例如：

```java
    int temp=nums[right];
    nums[right--]=nums[index];
    nums[index]=temp;
```

这样写代码行数是减少了，但是不便于理解。赋值语句类似于人的穴位，建议赋值语句都单独写一行(参考阿里巴巴java开发手册)。
