LeetCode: Sort Colors [075]

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.

Follow up:

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?

對隻有三種值0、1、2的數組進行排序，要求掃描一遍就排好序

排好序之後0在前，1在中，2在後

維護兩個p1和p2，p1指向0數組的尾部，p2指向2數組頭部

在維護一個p指針用于掃描數組，當p指向0時與p1置換，當p指向12時與p2置換

【注意，在給定的數組中，3個值不一定都出現】