[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.

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?

问题描述：简单地说就是，有一个数组，该数组中的值为0，1，2，要求使相同的值相邻，也就是相当于该数组排列的结果。

想法与前面的Remove Duplicats from Sorted Array类似，用一个变量i遍历数组，一个变量j指向前面全为0的后面一个元素，一个变量k指向后面全为2的前面一个元素。

当遍历到0时，如果i != j，就将A[i]与A[j]交换，如果i == j，说明i可以遍历后面一个元素了，而且j也可以往后面移动一个元素了，遍历到2时同理。当遍历到1时，直接遍历后面的元素。

class Solution {  
public:  
    void swap(int &a, int &b)  
    {  
        int temp = a;  
        a = b;  
        b = temp;  
    }  
  
    void sortColors(int A[], int n) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        int i = 0;  
        int j = 0, k = n-1;  
  
        while(i <= k) {  
            if(A[i] == 0) {  
                if(i != j) {  
                    swap(A[i], A[j]);  
                    ++j;  
                    continue;  
                }  
                else  
                    ++j;  
            }  
            else if(A[i] == 2) {  
                if(i != k) {  
                    swap(A[i], A[k]);  
                    --k;  
                    continue;  
                }  
                else  
                    --k;  
            }  
            ++i;  
        }  
    }  
};

补充：软件开发 , C++ ,