题目链接：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的数组进行排序。

  1. 计数排序

直接思路，计数排序。先遍历一遍数组，统计0，1和2的数量。接着再遍历1变数组，按照之前统计的数量重新对数组赋值。

不过则需要遍历两遍数组，下面的两种方法只需要遍历一遍数组。

时间复杂度：O(n)

空间复杂度：O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    void sortColors(int A[], int n)
    {
        int cnt[3] = {0, 0, 0};
        for(int i = 0; i < n; ++ i)
            ++ cnt[A[i]];
        
        for(int i = 0, j = 0; i < 3; ++ i)
            while(cnt[i] --)
                A[j ++] = i;
    }
};

  1. 左右指针

由于要排序的只有3种数字，所以只要把0放到左边，2放到右边，剩下的1放到中间即可。因此采用2个指针标记左边0的右侧位置和右边1的左侧位置，然后不断交换元素。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution
{
public:
    void sortColors(int A[], int n)
    {
        int zero = 0, two = n - 1;
        for(int i = 0; i <= two; ++ i)
        {
            while(A[i] == 2 && i < two)
                swap(A[i], A[two --]);
            while(A[i] == 0 && i > zero)
                swap(A[i], A[zero ++]);
        }
    }
};

  1. 利用索引

用3个变量zero、one、two分别标记已排好序的0，1和2的末端索引位置。当读取到0时候，3个变量均后移一位，同是置位；当读到1的时候，one和two后移一位并置位；当读到2的时候，只有two后移一位并置位。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution
{
public:
    void sortColors(int A[], int n)
    {
        int zero = 0, one = 0, two = 0;
        for(int i = 0; i < n; ++ i)
        {
            if(A[i] == 0)
            {
                A[two ++] = 2;
                A[one ++] = 1;
                A[zero ++] = 0;
            }
            else if(A[i] == 1)
            {
                A[two ++] = 2;
                A[one ++] = 1;
            }
            else
                A[two ++] = 2;
        }
    }
};