LeetCode Sort Colors：三色旗問題的單次遍歷解法

題目要求

數組含 0(紅)、1(白)、2(藍)，原地排序使同色相鄰且順序為 0,1,2。不可用庫排序，追求一趟掃描、常數空間。

解法一：三路快排分區（標準解）

public void sortColors(int[] A) {
    int red = -1, blue = A.length, p = 0;
    while (p < blue) {
        if (A[p] == 0) swap(A, ++red, p++);
        else if (A[p] == 2) swap(A, --blue, p);
        else p++;
    }
}
// 不變量：[0..red]=0, (red..p)=1, [blue..end)=2, [p..blue) 待檢查

解法二：直接覆寫（更直觀）

public void sortColors(int[] A) {
    int red = -1, white = -1, blue = -1;
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            A[++blue] = 2; A[++white] = 1; A[++red] = 0;
        } else if (A[i] == 1) {
            A[++blue] = 2; A[++white] = 1;
        } else { // 2
            A[++blue] = 2;
        }
    }
}
// 思路：統計見到的 0/1/2 個數，直接在尾部填入，利用藍指針始終指向已處理區末尾

複雜度對比

• 兩者均 O(n) 時間、O(1) 空間、單次遍歷。
• 解法一交換次數少（最多 n 次），解法二寫入次數固定（3n），但邏輯極簡無分支預測失敗。

兩趟計數排序（基準）

int cnt[3] = {0};
for (int x : A) cnt[x]++;
int idx = 0;
for (int c = 0; c < 3; c++)
    while (cnt[c]--) A[idx++] = c;