一、基礎概念

1.1 什么是三指針排序

三指針排序是一種特殊的分區排序算法，通過使用三個指針同時操作數組，將元素按照特定規則進行分類和排序。這種算法在處理包含有限種類值的數組時表現出色，最經典的應用是荷蘭國旗問題（Dutch National Flag Problem）。

1.2 三指針排序的基本思想

三指針排序的核心思想是：

• 使用三個指針將數組劃分為若干個區域
• 通過元素交換，確保每個區域內的元素都滿足特定條件
• 一次遍歷完成所有元素的分類排序

1.3 時間復雜度與空間復雜度

• 時間復雜度：O(n)，僅需一次遍歷
• 空間復雜度：O(1)，只使用常數級別的額外空間（幾個指針變量）

二、三指針排序的分類

2.1 按值分類的三指針排序

這是最常見的三指針排序應用，將數組中的元素按照特定值分為三類：

• 小于基準值的元素
• 等于基準值的元素
• 大于基準值的元素

2.2 多值三指針排序

處理有三種不同元素的數組，如荷蘭國旗問題中的紅、白、藍三色：

• 第一類元素（如0或紅色）
• 第二類元素（如1或白色）
• 第三類元素（如2或藍色）

三、三指針排序實現（荷蘭國旗問題）

3.1 數據結構設計

三指針排序主要操作簡單數組，不需要特殊的數據結構設計，只需要三個指針變量：

int low = 0;        // 指向第一類元素（0）的右邊界
int mid = 0;        // 遍歷指針，指向當前處理的元素
int high = n - 1;   // 指向第三類元素（2）的左邊界

3.2 排序算法實現

public class ThreePointerSort {/*** 三指針排序算法（荷蘭國旗問題）* 將數組中的0、1、2三種元素排序*/public void sortColors(int[] nums) {int low = 0;        // 0的右邊界int mid = 0;        // 當前處理元素int high = nums.length - 1;  // 2的左邊界while (mid <= high) {if (nums[mid] == 0) {// 當前元素為0，將其交換到左側區域swap(nums, low, mid);low++;mid++;} else if (nums[mid] == 1) {// 當前元素為1，保持位置不變mid++;} else { // nums[mid] == 2// 當前元素為2，將其交換到右側區域swap(nums, mid, high);high--;// 注意：這里mid不遞增，因為交換后的元素需要重新檢查}}}/*** 交換數組中兩個元素的位置*/private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

3.3 實現細節

三個區域劃分：

• [0, low-1]：所有等于0的元素
• [low, mid-1]：所有等于1的元素
• [mid, high]：待處理的元素
• [high+1, n-1]：所有等于2的元素

處理邏輯：

• 當前元素為0：將其交換到左側區域，low和mid都向右移動
• 當前元素為1：保持位置不變，只移動mid
• 當前元素為2：將其交換到右側區域，high向左移動，mid不動（需要重新檢查交換后的元素）

終止條件：

• mid > high時，所有元素都已處理完畢

四、執行示例

4.1 示例數組

以數組 [2, 0, 1, 2, 1, 0] 為例：

4.2 執行過程

1. 初始狀態：low=0, mid=0, high=5
   • 數組：[2, 0, 1, 2, 1, 0]
2. 第一步：nums[mid]=2
   • 交換 nums[mid] 和 nums[high]：[0, 0, 1, 2, 1, 2]
   • high=4, mid=0 (不變)
3. 第二步：nums[mid]=0
   • 交換 nums[low] 和 nums[mid]：[0, 0, 1, 2, 1, 2] (實際未變)
   • low=1, mid=1
4. 第三步：nums[mid]=0
   • 交換 nums[low] 和 nums[mid]：[0, 0, 1, 2, 1, 2] (實際未變)
   • low=2, mid=2
5. 第四步：nums[mid]=1
   • mid=3
6. 第五步：nums[mid]=2
   • 交換 nums[mid] 和 nums[high]：[0, 0, 1, 1, 2, 2]
   • high=3, mid=3
7. 第六步：nums[mid]=1
   • mid=4
8. 第七步：mid=4 > high=3，算法終止
   • 最終數組：[0, 0, 1, 1, 2, 2]

五、三指針擴展應用

5.1 快速排序的三路劃分

三路快排是三指針思想的另一個重要應用：

• 將數組劃分為小于、等于、大于基準值的三個部分
• 特別適合處理有大量重復元素的數組
• 可顯著提高快排效率

public void quickSort3Way(int[] arr, int low, int high) {if (low >= high) return;// 選擇基準值int pivot = arr[low];int lt = low;      // 小于區域右邊界int gt = high;     // 大于區域左邊界int i = low + 1;   // 當前處理元素while (i <= gt) {if (arr[i] < pivot) {swap(arr, lt++, i++);} else if (arr[i] > pivot) {swap(arr, i, gt--);} else {i++;}}// 遞歸排序小于和大于部分quickSort3Way(arr, low, lt - 1);quickSort3Way(arr, gt + 1, high);
}

5.2 處理特定數據集的分組

三指針排序可用于將數組按特定規則分為三組，如：

• 負數、零和正數
• 奇數、能被3整除的數和其他數
• 特定范圍內的元素、低于和高于范圍的元素

5.3 優化特定范圍查找

當需要找出數組中屬于特定值范圍的所有元素時，可使用三指針方法快速劃分：

public int[] findElementsInRange(int[] nums, int low, int high) {// 使用三指針劃分數組int[] result = new int[nums.length];int count = partitionByRange(nums, low, high);// 復制中間區域元素并返回// ...
}private int partitionByRange(int[] nums, int lowVal, int highVal) {int left = 0;int curr = 0;int right = nums.length - 1;while (curr <= right) {if (nums[curr] < lowVal) {swap(nums, left++, curr++);} else if (nums[curr] > highVal) {swap(nums, curr, right--);} else {curr++;}}return right - left + 1; // 返回范圍內元素數量
}

六、完整示例程序

6.1 處理三種顏色的完整實現

public class ThreeColorSort {public static void main(String[] args) {int[] colors = {2, 0, 1, 1, 0, 2, 1, 2, 0, 0, 1, 2};System.out.println("排序前: " + arrayToString(colors));sortColors(colors);System.out.println("排序后: " + arrayToString(colors));}public static void sortColors(int[] nums) {int low = 0;        // 0的右邊界int mid = 0;        // 當前處理元素int high = nums.length - 1;  // 2的左邊界while (mid <= high) {if (nums[mid] == 0) {swap(nums, low++, mid++);} else if (nums[mid] == 1) {mid++;} else { // nums[mid] == 2swap(nums, mid, high--);}}}private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}private static String arrayToString(int[] arr) {StringBuilder sb = new StringBuilder("[");for (int i = 0; i < arr.length; i++) {sb.append(arr[i]);if (i < arr.length - 1) {sb.append(", ");}}sb.append("]");return sb.toString();}
}

6.2 基于值范圍的三路劃分

public class ThreeWayPartition {public static void main(String[] args) {int[] arr = {5, 2, 8, 12, 3, 6, 9, 4, 10, 7};int lowVal = 4;int highVal = 8;System.out.println("原數組: " + arrayToString(arr));System.out.println("劃分范圍: [" + lowVal + ", " + highVal + "]");partitionByRange(arr, lowVal, highVal);System.out.println("劃分后: " + arrayToString(arr));}public static void partitionByRange(int[] nums, int lowVal, int highVal) {int left = 0;int curr = 0;int right = nums.length - 1;while (curr <= right) {if (nums[curr] < lowVal) {swap(nums, left++, curr++);} else if (nums[curr] > highVal) {swap(nums, curr, right--);} else {curr++;}}}private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}private static String arrayToString(int[] arr) {StringBuilder sb = new StringBuilder("[");for (int i = 0; i < arr.length; i++) {sb.append(arr[i]);if (i < arr.length - 1) {sb.append(", ");}}sb.append("]");return sb.toString();}
}

七、總結

三指針排序算法是一種高效、簡潔的算法，特別適合處理有限種類值的排序問題。

核心要點：

• 一次遍歷完成排序
• 原地操作，不需要額外空間
• 線性時間復雜度 O(n)
• 特別適合處理三種不同元素的排序問題

優點：

• 簡單易實現
• 高效（一次遍歷）
• 空間利用率高（原地操作）
• 穩定性可控

缺點：

• 僅適用于處理有限種類元素的排序
• 需要明確定義元素的優先級或類別

應用場景：

• 荷蘭國旗問題（三色排序）
• 快速排序的三路劃分優化
• 特定元素分組（如正數、零、負數）
• 數據預處理和清洗
• 基于特征值的數據分類

三指針排序是分治思想和指針技術的巧妙結合，體現了算法設計中"簡單而高效"的理念。掌握這一技術不僅有助于解決特定問題，更能啟發我們思考更廣泛的算法設計方法。