單次掃描三路快排分區：負數/零/正數原地分類算法

問題描述

給定包含負數、零、正數三類元素的數組，要求單次遍歷、原地重排，使所有負數在前、零在中、正數在後。

算法思想：三指針分區

維護三個區域邊界：

• p_neg：負數區尾後位置（下一個負數應放此處）
• p：當前掃描指針
• p_pos：正數區頭前位置（下一個正數應放此處）

不變量：[0, p_neg) 為負數，[p_neg, p) 為零，(p_pos, N-1] 為正數，[p, p_pos] 待處理。

完整代碼實現

#include <stdio.h>

#define N 9

void swap(int *p, int *q)
{
    int temp = *p;
    *p = *q;
    *q = temp;
}

int main()
{
    int array[N] = {-1, -3, 0, -2, 3, 2, -2, 0, 1};
    int *p_neg, *p, *p_pos;

    // 初始化：p_neg 指向開頭，p 掃描，p_pos 指向結尾
    for (p_neg = &array[0], p = &array[0], p_pos = &array[N-1];
         p <= p_pos; p++)
    {
        if (*p < 0) {              // 遇到負數
            swap(p, p_neg);        // 換到負數區
            p_neg++;               // 負數區擴展
        }
        if (*p > 0) {              // 遇到正數
            swap(p, p_pos);        // 換到正數區
            p_pos--;               // 正數區擴展
            p--;                   // 關鍵：換來的新元素需重新檢查
        }
        // *p == 0 時不動作，p 自然前進，零自動聚集在中間
    }

    // 驗證輸出
    for (int i = 0; i < N; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

關鍵細節解析

1. 指針初始化邏輯

p_neg = &array[0];   // 負數區從索引 0 開始
p = &array[0];       // 掃描從索引 0 開始
p_pos = &array[N-1]; // 正數區從索引 N-1 向前

2. 兩個 if 而非 else if

交換後 *p 值可能改變，需獨立判斷：

• 若換來負數，第一個 if 處理完 p_neg++，第二個 if 不滿足
• 若換來正數，第一個 if 不滿足，第二個 if 處理
• 若換來零，兩個 if 都不滿足，p 自然前進

3. p-- 的必要性

交換正數時，p_pos 位置的元素被換到 p，這個新元素未被檢查，p-- 抵消循環的 p++，使下輪仍檢查當前位置。

運行演示

初始：[-1, -3, 0, -2, 3, 2, -2, 0, 1]
p_neg=0, p=0, p_pos=8

p=0: -1 < 0 -> swap(0,0) p_neg=1
p=1: -3 < 0 -> swap(1,1) p_neg=2
p=2: 0  -> 無動作
p=3: -2 < 0 -> swap(3,2) p_neg=3  陣列：[-1,-3,-2,0,3,2,-2,0,1]
p=4: 3 > 0 -> swap(4,8) p_pos=7 p=3  陣列：[-1,-3,-2,0,1,2,-2,0,3]
p=3: 0  -> 無動作
p=4: 1 > 0 -> swap(4,7) p_pos=6 p=3  陣列：[-1,-3,-2,0,0,2,-2,1,3]
p=3: 0  -> 無動作
p=4: 0  -> 無動作
p=5: 2 > 0 -> swap(5,6) p_pos=5 p=4  陣列：[-1,-3,-2,0,0,-2,2,1,3]
p=4: 0  -> 無動作
p=5: -2 < 0 -> swap(5,3) p_neg=4  陣列：[-1,-3,-2,-2,0,0,2,1,3]
p=6: p > p_pos 結束

結果：[-1, -3, -2, -2, 0, 0, 2, 1, 3] ✓

複雜度與特性

• 時間：O(N) —— 單次遍歷
• 空間：O(1) —— 原地交換
• 穩定性：不穩定（交換改變相對順序）
• 應用：快速排序三路分區、荷蘭國旗問題

本文整理自「天才鳥蛋」博客，原文地址：https://curely.blog.51cto.com/1627940/1297308