# 148.Sort Colors

## 1.Description(Medium)

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.

### Notice

You are not suppose to use the library's sort function for this problem.\
You should do it in-place (sort numbers in the original array).

**Example**

Given`[1, 0, 1, 2]`, sort it in-place to`[0, 1, 1, 2]`

[**Challenge**](https://www.lintcode.com/en/problem/sort-colors/#challenge)

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?

## 2.Code

一开始想到的就是计数排序，但是计数排序需要两边扫描，第一遍统计红，白，蓝的数目，第二遍生成新数组。

考虑到题目要求one pass。这就意味着类似于链表的双指针问题，这里也要track两个index，一个是red的index，一个是blue的index，两边往中间走。

i从0到blue index扫描，

遇到0，放在red index位置，red index后移；

遇到2，放在blue index位置，blue index前移；

遇到1，i后移。

扫描一遍得到排好序的数组。时间O(n)，空间O(1)

```
 public void sortColors(int[] nums) {
        if(nums==null || nums.length==0){
            return;
        }
        int redindex=0;
        int blueindex=nums.length-1;
        int i=0;
        //注意这里是<=
        while(i<=blueindex){
            if(nums[i]==0){
                swap(nums,redindex,i);
                redindex++;
                i++;
            }
            else if(nums[i]==2){
                swap(nums,blueindex,i);
                blueindex--;
            }
            else if(nums[i]==1){
                i++;
            }
        }

    }

    public void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
```

这里要求one pass完成排序，需要利用只有数组元素只有3个数的特性，否则无法完成。排序完成后一定是0...01...12....2，所以可以扫描数组，当遇到0时，交换到前部，当遇到1时，交换到后部。用双指针left, right来记录当前已经就位的0序列和2序列的边界位置。

假设已经完成到如下所示的状态：

0......0 1......1 x1 x2 .... xm 2.....2

```
          \|           \|               \|

        left        cur          right
```

(1) A\[cur] = 1：已经就位，cur++即可

(2) A\[cur] = 0：交换A\[cur]和A\[left]。由于A\[left]=1或left=cur，所以交换以后A\[cur]已经就位，cur++，left++

(3) A\[cur] = 2：交换A\[cur]和A\[right]，right--。

**由于xm的值未知，cur不能增加，继续判断xm。**&#x63;ur>right扫描结束。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/7.two-pointers/148sort-colors.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.