dustfree's blog
0%

Sort Colors

Posted on In ,

Question

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]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
@param: int[] input numbers
@result: sorted with numbers in 0,1,2
Algorithm: 以1为pivot来进行partition
*/
public void sortColors(int[] nums) {
    if (nums.length <= 1) {
        return;
    }    
    int left = 0, right = nums.length-1;
    int i = 0;
    while (i <= right) {
        if (nums[i] == 0) {
            swap(nums, i, left);
            left++;
            i++;
        }else if (nums[i] == 1) {
            i++;
        }else if (nums[i] == 2) {
            swap(nums, i, right);
            right--;                
        }
    }        
}

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