LeetCode-75~Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:You are not suppose to use the library's sort function for this problem.
给定一个数组，由n个分别涂有红、白、蓝颜色的对象组成，给数组排序，使得有相同颜色的对象相邻，其中，颜色顺序为红、白、蓝。
使用0、1、2分别表示红、白、蓝
注意：不建议使用库中排序函数解决问题

算法分析

利用三个索引标志，begin、end分别表示白色的首尾位置。

Java代码

public class Solution {
    public void sortColors(int[] nums) {
        int begin = 0, end = nums.length - 1, curr = 0;//begin和end分别表示颜色为1的开始和结尾索引
        while(curr <= end) {//有等号是因为我们至判断nums[curr]，并未判断nums[end]，因此最后一步就需要判断nums[end]
            if (nums[curr] == 0) {
                if (curr != begin) {
                    int temp = nums[curr];
                    nums[curr] = nums[begin];
                    nums[begin] = temp;
                }
                curr ++;
                begin ++;
            } else if (nums[curr] == 1) {
                curr ++;
            } else if (nums[curr] == 2) {
                if (curr != end) {
                    int temp = nums[curr];
                    nums[curr] = nums[end];
                    nums[end] = temp;
                }
                end --;
                //curr ++;此处curr不能加yi的原因是，与end索引处置换后的值还未判断，需要再进行判断一次
            }
        }
    }
}

参考

oschina
LeetCode