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.

分析：

start表示last 0之后的元素，mid表示last 1之后的元素，end表示first 2之前的元素。

这道题目注意while的条件是mid <= end，只是小于还不够。

解法：

class Solution{
public:
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */    
    void sortColors(vector<int> &nums) {
        // write your code here
        if (nums.size() == 0) {
            return;
        }
        int start = 0;
        int mid = 0;
        int end = nums.size() - 1;
        while (mid <= end) {
            if (nums[mid] == 0) {
                swap(nums[start], nums[mid]);
                start++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[end]);
                end--;
            }
        }
    }
};