本文介紹一種時間復雜度O(n)、空間復雜度O(1)的優雅解法，通過雙指針技術實現顏色分類的一趟掃描排序

問題描述

給定一個包含紅色（0）、白色（1）和藍色（2）的數組 nums，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色的順序排列。

示例：

輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]

算法思路：三指針分區法

核心思想

使用三個指針將數組分為四個區域：

1. [0, p0)：已排序的0區域
2. [p0, curr)：已排序的1區域
3. [curr, p2]：待處理區域
4. (p2, end]：已排序的2區域

指針定義

• p0：指向下一個0應放置的位置（0區域的右邊界）
• p2：指向下一個2應放置的位置（2區域的左邊界）
• curr：當前遍歷指針，負責處理元素交換

Java實現

class Solution {public void sortColors(int[] nums) {if (nums == null || nums.length < 2) return;int p0 = 0;                   // 0區域右邊界int p2 = nums.length - 1;     // 2區域左邊界int curr = 0;                 // 當前遍歷指針while (curr <= p2) {switch (nums[curr]) {case 0:// 將0交換到0區域swap(nums, curr++, p0++);break;case 1:// 1保留在中間區域curr++;break;case 2:// 將2交換到2區域swap(nums, curr, p2--);// 注意：curr不自增，需檢查交換來的新元素break;}}}// 輔助交換函數private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

算法執行流程

1. 初始化指針：

   • p0 = 0（0區域起始位置）
   • p2 = nums.length-1（2區域起始位置）
   • curr = 0（從數組開頭遍歷）

2. 元素處理邏輯：

   • 遇到0：與p0交換，p0和curr右移
   • 遇到1：跳過，curr右移
   • 遇到2：與p2交換，p2左移（curr不變）

3. 終止條件：curr > p2（所有元素處理完畢）

關鍵問題解析：為什么交換0后不需要重新檢查？

交換0時的兩種情況分析

情況	條件	交換前狀態	交換后狀態
情況1	curr > p0	nums[p0] = 1	nums[curr] = 1
情況2	curr == p0	自身交換	保持不變

詳細解釋：

1. 當curr > p0時：

   • p0位置必定是1（因為0區域和1區域已排序）
   • 交換后curr位置變為1 → 可直接跳過處理（1屬于中間區域）

2. 當curr == p0時：

   • 自身交換無實際變化
   • 元素保持0 → 屬于已排序區域

結論：交換0后curr位置的新元素只可能是0或1，都無需再次處理，因此可以直接移動curr指針。

復雜度分析

指標	值	說明
時間復雜度	O(n)	單次遍歷完成排序
空間復雜度	O(1)	僅使用常數級額外空間

示例演示（輸入：[2,0,2,1,1,0]）

步驟	操作	數組狀態	指針變化
1	初始狀態	[2,0,2,1,1,0]	p0=0, p2=5, curr=0
2	處理2：交換curr?p2	[0,0,2,1,1,2]	p2=4
3	處理0：交換curr?p0	[0,0,2,1,1,2]	p0=1, curr=1
4	處理0：交換curr?p0	[0,0,2,1,1,2]	p0=2, curr=2
5	處理2：交換curr?p2	[0,0,1,1,2,2]	p2=3
6	處理1：跳過	[0,0,1,1,2,2]	curr=3
7	處理1：跳過	[0,0,1,1,2,2]	curr=4 > p2（結束）

總結

雙指針法解決顏色分類問題的核心在于：

1. 通過p0和p2維護已排序區域
2. curr指針動態處理待排序區域
3. 巧妙利用交換操作實現元素歸位
4. 利用數組分區特性優化操作步驟（交換0后無需重檢）

該算法是荷蘭國旗問題的經典解法，體現了雙指針技術在數組原地操作中的高效性，是面試中的高頻考點。