# Sort Colors

Medium

Given an array with_n_objects colored red, white or blue, sort themin-placeso 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]
``````

• 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?

## Solution

https://www.jiuzhang.com/solution/sort-colors/\#tag-other

left 的左侧都是 0（不含 left）
right 的右侧都是 2（不含 right）
index 从左到右扫描每个数，如果碰到 0 就丢给 left，碰到 2 就丢给 right。碰到 1 就跳过不管。

``````
public class Solution {
/**
* @param nums: A list of integer which is 0, 1 or 2
* @return: nothing
*/
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

int pl = 0, pr = nums.length - 1;
int index = 0;
while (index <= pr) {
if (nums[index] == 0) {
swap(nums, pl, index);
index++;
pl++;
}
else if (nums[index] == 2) {
swap(nums, pr, index);
pr--;
}
else {
index++;
}
}
}

private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
``````

Counting Sort (Buckets) - (0 ms, faster than 100.00%)

``````class Solution {
private static final int MAX = 3;

public void sortColors(int[] nums) {
int[] buckets = new int[MAX];

for(int num : nums) {
buckets[num]++;
}

int i = 0;
for(int val = 0; val < MAX; val++) {
for(int count = 0; count < buckets[val]; count++) {
nums[i++] = val;
}
}
}
}
``````

## Reference

https://leetcode.com/problems/sort-colors/discuss/26500/Four-different-solutions