本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

二、解题思路

1.排序算法

说到排序，那肯定是使用排序算法啦！

时间复杂度分析

假设使用快速排序

• O(nlogn)

空间复杂度分析

假设使用快速排序

• O(1)

2.单指针

想想还有什么优化方向没有？
已有信息：

• 只有三种颜色，也就是只有0，1，2三个数字
• 按红，白，蓝排序，也就是0，1，2排序

只有三个数字的话，那我们用指针扫描数组把0放左边，2放右边。
那我们可以扫描两遍，第一遍把0移到左边，第二遍把2移到右边。

时间复杂度分析

• O(2n)

空间复杂度分析

• O(1)

3.双指针

我们发现单指针在第一遍扫描到2的时候没有做任何操作，因而需要2遍扫描。
那我们能在一遍扫描中完成排序吗？
答案是可以的。我们可以增加一个指针记录1的位置（其实记录2的位置也可以）。

时间复杂度分析

• O(n)

空间复杂度分析

• O(1)

三、代码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}
复制代码

不晓得我讲清楚了没有，请大家多多指教。
今日打卡结束！