LeetCode每日一题：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.
click to show follow up.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

问题分析

这道题简单的解法题目都规定不能使用，不能调用库函数sort，不能采用循环两遍的复写A算法，这道题只能遍历一遍。
设三个指针，left表示从左往右第一个1的数，right表示从右往左第一个不是2的数，i从0开始向最末尾前进，遇到0，就与left交换，遇到2就与right交换，这样一趟走下来就是有序的了。

代码实现

public void sortColors(int[] A) {
        int left = 0;
        int right = A.length - 1;
        int i = 0;
        while (i <= right) {
            if (A[i] == 0) {
                swap(A, left, i);
                left++;
                i++;
            } else if (A[i] == 2) {
                swap(A, i, right);
                right--;
            } else i++;
        }
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }