[LEETCODE] Sort Colors

[LEETCODE] 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.

思路:

定义一个red指针在最左，一个blue指针在最右。

一个变量从0开始向blue指针扫描：

遇到red(0)  就跟red 指针对换，red 指向下一个，扫描变量指向下一个；

遇到blue(2)就跟blue指针对换，blue指向前一个，扫描变量不动，因为需要判断被换了的值。

代码:

An one-pass algorithm using only constant space

    void sortColors(int A[], int n) {

        int red  =0  ;

        int blue =n-1;

        int i=0;

        while(i<blue+1){

            if(A[i] == 0){

                std::swap(A[red], A[i]);

                red++;

                i++;

                continue;

            }

            if(A[i] == 2){

                std::swap(A[blue],A[i]);

                blue--;

                continue;

            }

            i++;

        }

    }