【LeetCode & 剑指offer刷题】查找与排序题11：Sort Colors

Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place 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.

Example:

Input: [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

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 a one-pass algorithm using only constant space?

C++

//问题：颜色排序（以后看可不可以用partition）
//双指针法，只能用于只有三类的排序，不过只需一次遍历
#include <algorithm>
class Solution
{
public:
    void sortColors(vector<int>& A)
    {
        int left=0,right=A.size()-1;//双指针，left从左边扫描，right从右边扫描
        for(int i= 0;i<=right;i++) //扫描到right即可
        {
            if(A[i] == 0) swap(A[i++],A[left++]); //将0换到左边
            else if(A[i] == 2) swap(A[i--],A[right--]); //将2换到右边，i--是以免right换过来的值为0（抵消for循环中的i++）
        }
    }
};
//存储后移法（相当于直接插入排序,只不过预先知道了有哪些数，故简单一点）
class Solution
{
public:
    void sortColors(vector<int>& A)
    {
        int n0,n1,n2;//类别索引
        n0 = n1 = n2 = 0;
        for(int i = 0; i<A.size(); i++)
        {
            switch(A[i])
            {
                case 0:
                    A[n2++] = 2; A[n1++] = 1; A[n0++] = 0;//后面的元素往后移
                    break;
                case 1:
                    A[n2++] = 2; A[n1++] = 1;
                    break;
                case 2:
                    A[n2++] = 2;
            }
        }
    }
};
 
//计数排序，需要两次遍历
class Solution
{
public:
    void sortColors(vector<int>& nums)
    {
        int count[3] = {0};//用于统计每个颜色出现的次数
        for(int i=0;i<nums.size();i++) //统计直方图
            count[nums[i]]++;
      
        for(int i = 0,index = 0;i<3;i++) //排序
            for(int j = 0; j<count[i];j++)
                nums[index++] = i;
    }
};