一.题目介绍

1.题目来源

链接：LeetCode

2.题目

给定一个包含红色、白色和蓝色、共n个元素的数组nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1] 输出：[0,1,2]

二.具体实现

1.实现思路

通过提示我们可以容易想到头尾各用一个指针，然后一次遍历，遇到红色就与头部置换，遇到蓝色就与尾部置换，其中遇到蓝色时，需要判断尾部之前为红色的场景，此时通过将index减一，可以避免代码添加额外判断。

2.实现代码

1)自己的实现方式

public void sortColors(int[] nums) {
    int redIndex = 0;
    int blueIndex = nums.length - 1;
    for (int index = 0; index <= blueIndex; index++) {
        if (nums[index] == 0) {
            swap(nums, redIndex, index);
            redIndex++;
        }
        if (nums[index] == 2) {
            swap(nums, blueIndex, index);
            blueIndex--;
            index--; 
        }
    }
}
private void swap(int[] nums, int x, int y) {
    int temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}
复制代码

2)题友的实现方式

单指针:对数组进行两次遍历。在第一次遍历中，将数组中所有的00交换到数组的头部。在第二次遍历中，将数组中所有的11交换到头部的00之后。此时，所有的22都出现在数组的尾部，这样就完成了排序。

3.运行结果

三.题后思考

可以看到题目已经有限制使用现有函数sort了，也就是很多时候我们在解题的时候会使用到现有的函数，算是偷懒了，这也是一个提醒，做题的时候一定要把题目审清楚，不然写完了才发现不对。