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

Note:
You are not suppose to use the library's sort function for this problem.

思路：

这里要求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。

cur > right扫描结束。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: void sortColors(int A[], int n) { int left=0, right=n-1; int i = 0; while(i<=right) { if(A[i]==0) swap(A[i++],A[left++]); else if(A[i]==1) i++; else if(A[i]==2) swap(A[i],A[right--]); } } };