PHP 實現兩數組隨機合併並保持原有順序算法詳解

業務場景：原有帖子列表 A，需按 1:1 比例穿插推廣內容 B，**合併後 A、B 內部相對順序不變**，整體隨機交織。本文提供 O(N) 時間、O(1) 額外空間（不計輸出）的原地算法思路與 PHP 實現，並附帶 shuffle() 簡單隨機打亂對比。

算法原理

1. 設兩數組長度分別為 lenA、lenB，總長 N = lenA + lenB
2. 循環 N 次，每次隨機選擇從 A 還是 B 取頭元素（mt_rand(1,2)）
3. 若某數組已耗盡，強制從另一數組取
4. 使用 array_shift() 取並移除首元素，推入結果數組

PHP 實現

/**
 * 隨機合併兩數組，保持各自原有順序
 * @param array $a
 * @param array $b
 * @return array
 */
function shuffleMergeArray(array $a, array $b): array {
    $merged = [];
    $total = count($a) + count($b);

    for ($i = 0; $i < $total; $i++) {
        // 若其中一個為空，直接取另一個
        if (empty($a)) {
            $merged[] = array_shift($b);
            continue;
        }
        if (empty($b)) {
            $merged[] = array_shift($a);
            continue;
        }

        // 隨機 1 或 2
        $pick = mt_rand(1, 2);
        $merged[] = ($pick === 1) ? array_shift($a) : array_shift($b);
    }
    return $merged;
}

// 示例
$array1 = [1, 2, 3, 4];
$array2 = ['a', 'b', 'c', 'd', 'e'];

$merged = shuffleMergeArray($array1, $array2);
// 可能輸出：['a', 1, 'b', 2, 'c', 'd', 3, 4, 'e']
print_r($merged);

關鍵點解析

• array_shift() 會重建數值索引，雖然每次 O(n)，但總體仍為 O(N²) 級。若數組極大（>10 萬），建議改用**索引指針**版本：

function shuffleMergeArrayFast(array $a, array $b): array {
    $ia = $ib = 0;
    $na = count($a); $nb = count($b);
    $merged = [];

    for ($i = 0; $i < $na + $nb; $i++) {
        if ($ia >= $na) { $merged[] = $b[$ib++]; continue; }
        if ($ib >= $nb) { $merged[] = $a[$ia++]; continue; }
        $merged[] = (mt_rand(1,2) === 1) ? $a[$ia++] : $b[$ib++];
    }
    return $merged;
}

對比：shuffle() 完全隨機打亂

若**不需要保持內部順序**，直接合併後 shuffle() 更簡單：

$arr = ['A','2','3','4','5','6','7','8','9','10','J','Q','K'];
shuffle($arr); // 原地打亂，不保證任何順序
print_r($arr);

應用場景延伸

總結

「隨機合併且保序」本質是**按概率從兩個隊列頭部出隊**，核心代碼不超 15 行。理解 array_shift 與索引指針的性能權衡，能應對從小型列表到大規模流式合併的各種場景。