> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/sort-colors.md).

# 75. 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?

## Thoughts

对只由0，1和2构成的数组排序。和bucket sort思想类似，看作有0，1和2三个bucket，分别由两个指针隔开，首指针前的都是排好的0，尾指针后的都是排好的2，0,...,0,1(j),...,1, x(i),x,x(k), 2,2,...,2，然后遍历让让i指向待排元素，j和k分别指向当前已经就位的下一个位置。对nums\[i]作判断，当nums\[i]==1，未知边界指针i++；当nums\[i]==0, 把它和j swap，++j。当nums\[i]==2, 和right swap，--k。由于交换回i的x值未知，因此不能直接i++，应继续循环以检查i的新值是多少。

## Code

```cpp
/*
 * @lc app=leetcode id=75 lang=cpp
 *
 * [75] Sort Colors
 */

// @lc code=start
class Solution {
public:
    void sortColors(vector<int>& nums) {
        const int N = nums.size();
        for (int i = 0, j = 0, k = N - 1; i <= k;) {
            if (nums[i] == 0 && j < i) swap(nums[i], nums[j++]);
            else if (nums[i] == 2 && k > i) swap(nums[i], nums[k--]);
            else ++i;
        }
    }
};
// @lc code=end


```

```cpp
/*
 * @lc app=leetcode id=75 lang=cpp
 *
 * [75] Sort Colors
 *
 * https://leetcode.com/problems/sort-colors/description/
 *
 * algorithms
 * Medium (43.05%)
 * Likes:    1897
 * Dislikes: 168
 * Total Accepted:    349.1K
 * Total Submissions: 810.6K
 * Testcase Example:  '[2,0,2,1,1,0]'
 *
 * 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?
 * 
 * 
 */
class Solution {
public:
    void sortColors(vector<int>& nums) {
        const int N = nums.size();
        int l = 0, r = N - 1, i = 0;
        while (i <= r) {
            if (nums[i] == 0) {
                swap(nums[i], nums[l++]);
                if (i < l) ++i; // if 可以去掉让i直接++，但不好理解
            }
            else if (nums[i] == 1) ++i;
            else swap(nums[i], nums[r--]);
        }
    }
};


```

## Analysis

Errors:

1. i = 1初始必须为0，如\[2,1]
2. i < right，必须是i<=right, 如\[1,0], 由于nums\[i] == 1了，紧接着又i < right，不执行了

时间复杂度O(n), 空间O(1)

## 当有k种颜色需要排序

这时就无法1 pass做出来了。但有一个general的模板解决这类问题，即bucket sort.

依序每次把nums中和i相等的换到前面的相应位置。

以下是别人写的代码

```
public class Solution {
    public void sortColors(int[] nums) {
        int[] cand = {0, 1, 2};
        int start=0;
        for(int i=0;i<3;i++){
            while(start<nums.length && nums[start]==cand[i]) start++;
            for(int j=start;j<nums.length;j++){
                if(nums[j]==cand[i]){
                    swap(nums, j, start++);
                }
            }
        }
        return;
    }
    public void swap(int[] nums, int a, int b){
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}
```

时间复杂度O(nk)