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.

大體意思是有一個(gè)顏色數(shù)組，包含紅、白、藍(lán)三種類型的顏色亂序排列在一起，讓我們重新排列數(shù)組元素，使得同顏色的元素相鄰。這個(gè)問題也叫荷蘭國旗問題，因?yàn)槲覀兛梢詫⒓t、白、藍(lán)三色想象成條狀物，有序排列后正好組成荷蘭國旗。

解法一：

1. 遍歷數(shù)組，統(tǒng)計(jì)紅、白、藍(lán)（0，1，2）三種元素的個(gè)數(shù)
2. 根據(jù)三種顏色元素的個(gè)數(shù)重排數(shù)組

這種算法利用了計(jì)數(shù)排序的思想，時(shí)間復(fù)雜度O(n)，代碼如下

public class Solution {
    public void sortColors(int[] nums) {
        int red = 0;
        int white = 0;
        int blue = 0;
        for (int i = 0; i < nums.length; i++) {
            switch (nums[i]) {
                case 0:
                    red++;
                    break;
                case 1:
                    white++;
                    break;
                case 2:
                    blue++;
                    break;
                default:
                    break;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i < red) {
                nums[i] = 0;
            } else if (i < red + white) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
}

解法二：

利用快速排序partition過程的思想，我們可以把數(shù)組分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2），每一個(gè)元素必屬于其中之一。當(dāng)我們把前部和后部各排在數(shù)組的前邊和后邊，中部自然就排好了。

設(shè)置兩個(gè)指針begin和end，begin指向前部末尾的下一個(gè)元素（剛開始默認(rèn)前部無0，所以begin指向第一個(gè)位置），end指向后部開頭的前一個(gè)位置（剛開始默認(rèn)后部無2，所以end指向最后一個(gè)位置），然后設(shè)置一個(gè)遍歷指針current，從頭開始進(jìn)行遍歷。

1. 若遍歷到的位置為1，則說明它一定屬于中部，中部的我們都不動(dòng)，然后current繼續(xù)向后移動(dòng)一個(gè)位置。

2. 若遍歷到的位置為0，則說明它一定屬于前部，于是就和begin位置進(jìn)行交換，然后begin向后移動(dòng)一個(gè)位置。由于從begin位置交換過來的元素一定是已經(jīng)遍歷過的元素，所以current也向后移動(dòng)一個(gè)位置。

3. 若遍歷到的位置為2，則說明它一定屬于后部，于是就和end位置進(jìn)行交換，然后end向前移動(dòng)一個(gè)位置。由于從end位置交換過來的元素我們并沒有遍歷過，它可能是屬于前部的，所以此時(shí)current并不向后移動(dòng)。

partition過程圖

上述過程的代碼如下，時(shí)間復(fù)雜度也為O(n)

public class Solution {
    public void sortColors(int[] nums) {
        int begin = 0;
        int end = nums.length - 1;
        int cur = 0;
        while (cur <= end) {
            if (nums[cur] < 1) {
                swapElement(nums, begin, cur);
                begin++;
                cur++;  // 從begin位置交換過來的元素一定是已經(jīng)遍歷過的元素
            } else if (nums[cur] > 1) {
                swapElement(nums, end, cur);
                end--;
                // 從end位置交換過來的元素我們并沒有遍歷過
            } else {
                cur++;
            }
        }
    }

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

對(duì)于快速排序，雖然它不能保證在最壞情況下仍為O(nlogn)的時(shí)間復(fù)雜度（主要原因在于基準(zhǔn)的不確定性，有可能遭遇每次選取的基準(zhǔn)都是最值的情況），但它的partition過程仍有著廣泛的應(yīng)用價(jià)值。
著名的BFPRT算法就是先通過巧妙的方式（中位數(shù)的中位數(shù)）選取基準(zhǔn)，再利用快速排序的partition過程，實(shí)現(xiàn)了在最壞情況下仍然可以在線性時(shí)間復(fù)雜度內(nèi)從任意的無序數(shù)組中找到第K?。ù螅┑脑兀唇鉀Qtop K問題。