ACM 01排序問題解析

問題描述

給定一個只包含 0 和 1 的序列，要求對其進行排序（所有 0 在前，1 在後）。這是一個經典的計數排序/雙指針分區問題。

算法思路

• 計數法：遍歷一次統計 0 的個數 cnt0，然後前 cnt0 位填 0，後填 1。時間 O(n)，空間 O(1)。
• 雙指針原地分區：左指針 i 找 1，右指針 j 找 0，i 時交換。同樣 O(n)，O(1)，且只需一次掃描。
• 標準庫：sort(arr, arr+n) 或 stable_partition。

void sort01(int a[], int n){
    int i=0, j=n-1;
    while(i