已排序陣列中插入新元素,需保持升序/降序。適用於:即時排行榜、日誌插入、優先級佇列維護等場景。
| 方案 | 時間複雜度 | 空間複雜度 | 適用場景 |
|---|---|---|---|
| 線性掃描 + array_splice | O(n) | O(n) | 小陣列 (<1000)、簡單場景 |
| 二分查找 + array_splice | O(log n) 查找 + O(n) 移動 | O(n) | 中大型有序陣列、高頻插入 |
| 重新排序 (array_push + sort) | O(n log n) | O(n) | 批次插入後統一排序 |
| SplPriorityQueue | O(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
// 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。原文算法邏輯正確但實作繁瑣且無邊界檢查,生產環境請使用本文優化版或成熟庫。