萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 有序陣列插入元素並保持原序:二分查找優化版與內建函數對比

問題場景

已排序陣列中插入新元素,需保持升序/降序。適用於:即時排行榜、日誌插入、優先級佇列維護等場景。

方案對比

方案時間複雜度空間複雜度適用場景
線性掃描 + array_spliceO(n)O(n)小陣列 (<1000)、簡單場景
二分查找 + array_spliceO(log n) 查找 + O(n) 移動O(n)中大型有序陣列、高頻插入
重新排序 (array_push + sort)O(n log n)O(n)批次插入後統一排序
SplPriorityQueueO(log n) 入隊/出隊O(n)優先級佇列、需頻繁取最大/最小值

優化版:二分查找插入 (支援重複值、升序/降序)

<?php
/**
 * 有序陣列插入元素 (保持升序)
 * @param array $sortedArray 參考傳遞,已排序陣列
 * @param mixed $value 待插入值
 * @param callable|null $compare 自定義比較函數 (預設升序)
 * @return int 插入位置索引
 */
function sortedArrayInsert(array &$sortedArray, mixed $value, ?callable $compare = null): int
{
    $compare ??= fn($a, $b) => $a <=> $b; // PHP 7+ 太空船運算子
    
    $low = 0;
    $high = count($sortedArray);
    
    // 二分查找插入位置 (左邊界:相等值插在現有元素之前)
    while ($low < $high) {
        $mid = (($high - $low) >> 1) + $low;
        if ($compare($sortedArray[$mid], $value) < 0) {
            $low = $mid + 1;
        } else {
            $high = $mid;
        }
    }
    
    // 插入
    array_splice($sortedArray, $low, 0, [$value]);
    return $low;
}

/**
 * 有序陣列批次插入 (優化多次移動)
 */
function sortedArrayInsertBatch(array &$sortedArray, array $values, ?callable $compare = null): void
{
    // 合併後單次排序:O((n+m) log(n+m)) vs m * O(n) 逐個插入
    $sortedArray = array_merge($sortedArray, $values);
    usort($sortedArray, $compare ?? fn($a, $b) => $a <=> $b);
}

// 測試
$arr = [10, 20, 30, 40, 50];
sortedArrayInsert($arr, 25);
sortedArrayInsert($arr, 5);
sortedArrayInsert($arr, 55);
sortedArrayInsert($arr, 30); // 重複值
var_dump($arr); 
// [5, 10, 20, 25, 30, 30, 40, 50, 55]
?>

原文算法分析與改進

<?php
// 原文算法問題分析
function array_intsort_original($array, $num) {
    // 問題 1: 假設陣列非空,未處理空陣列
    // 問題 2: 假設陣列已排序,無驗證
    // 問題 3: 邏輯複雜,使用 array_slice 多次複製陣列 (O(n) 空間)
    // 問題 4: 僅支援數值陣列,不支援物件/字串/自定義比較
    // 問題 5: 重複值處理邏輯不明確
}
?>

內建函數替代方案 (PHP 8.0+)

<?php
// array_is_list() 檢查是否為列表 (連續數字鍵)
$arr = [10, 20, 30];
$arr[] = 25;
sort($arr, SORT_NUMERIC | SORT_FLAG_CASE); // 簡單粗暴但有效

// SplFixedArray 固定大小陣列 (效能更高,但需預知大小)
// 不適合動態插入場景
?>

實戰:即時排行榜維護

<?php
class Leaderboard
{
    private array $scores = []; // [userId => score]
    private array $sorted = []; // 緩存排序結果 [userId, score] 按分數降序
    private bool $dirty = false;

    public function updateScore(string $userId, int $score): void
    {
        $this->scores[$userId] = $score;
        $this->dirty = true;
    }

    public function getTop(int $limit = 10): array
    {
        if ($this->dirty) {
            // 重建排序
            arsort($this->scores); // 保持鍵值關聯,按值降序
            $this->sorted = array_slice($this->scores, 0, $limit, true);
            $this->dirty = false;
        }
        return $this->sorted;
    }

    public function getRank(string $userId): ?int
    {
        if ($this->dirty) $this->getTop(count($this->scores));
        $keys = array_keys($this->sorted);
        $pos = array_search($userId, $keys, true);
        return $pos !== false ? $pos + 1 : null;
    }
}

// 使用
$lb = new Leaderboard();
$lb->updateScore('user1', 1500);
$lb->updateScore('user2', 1800);
$lb->updateScore('user3', 1200);
print_r($lb->getTop(2)); // user2, user1
echo $lb->getRank('user1'); // 2
?>

總結

有序陣列插入核心權衡:查找 O(log n) + 移動 O(n)。單次插入用二分查找 + array_splice();批次插入用合併後 sort()。高頻更新排行榜場景建議使用「臟標記 + 定期重排」或 SplPriorityQueue。原文算法邏輯正確但實作繁瑣且無邊界檢查,生產環境請使用本文優化版或成熟庫。

copyright © 萬盛學電腦網 all rights reserved