荷兰三色旗问题

问题陈述

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

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

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
设置三个指针，分别指向首尾和当前位，遍历数组，如果为2则交换到尾部，为0则交换到首部。
**/
class Solution{
    public void sortColor(int[] nums){
        int p0=0,p2=nums.length-1,cur=0;
        
        int temp;
        while(cur<=p2){
            if(nums[cur]==0){
                temp=nums[p0];
                nums[p0++]=nums[cur];
                nums[cur++]=temp;
            }
            if(nums[cur]==2){
                temp=nums[p2];
                nums[p2++]=nums[cur];
                nums[cur++]=temp;
            }
            else{
                cur++;
            }
        }
    }
}