別再每插入一次就 .sort() 了！我寫了個(gè) 2KB 的 TypeScript 排序容器

你肯定遇到過這種場(chǎng)景：維護(hù)一個(gè)排行榜、一個(gè)訂單簿，或者需要查出某個(gè)區(qū)間內(nèi)的所有元素。原生 JavaScript 給了你 Array、Set、Map，但沒有一種能讓你在插入時(shí)就自動(dòng)保持有序。于是只好每次塞完數(shù)據(jù)，手賤再調(diào)一次 .sort()。數(shù)據(jù)少的時(shí)候還行，一旦規(guī)模上來，這招就成了性能天坑——數(shù)據(jù)明明 99.9% 已經(jīng)有序，你還得花 O(n log n) 的代價(jià)重新排一遍，再硬的 CPU 也經(jīng)不起這么虐。

Python 社區(qū)很早就解決了這件事。那會(huì)兒有個(gè)純 Python 實(shí)現(xiàn)的 sortedcontainers 庫(kù)，用了一種挺“雞賊”但好用的設(shè)計(jì)：把數(shù)據(jù)塞進(jìn)很多個(gè)小列表里，而不是去折騰平衡樹。我當(dāng)時(shí)看到就想，TypeScript 能不能也來一個(gè)？于是照著原版思路，寫了個(gè) sorted-collections，雖然是從 Python 搬磚過來的，但所有實(shí)現(xiàn)都是按 JavaScript 的地形重新設(shè)計(jì)過，沒直接抄一行代碼。

這個(gè)庫(kù)給了你 SortedList、SortedSet、SortedMap 三個(gè)容器，全部天然排序，不再需要手動(dòng) sort。插入操作能達(dá)到 O(log n) 的查找耗時(shí)，基于桶的索引讓按位置取元素控制在 O(√n)。重要的是，它沒有引入任何運(yùn)行時(shí)依賴，壓縮后體積才約 2KB，類型聲明全內(nèi)置，同時(shí)支持 ESM 和 CJS 格式。在 CI 管道里，還掛了 publint、arethetypeswrong 和 size-limit，提醒你不能在任何細(xì)節(jié)上滑坡。

快速看一下 API。實(shí)例化一個(gè) SortedList 時(shí)，亂序塞進(jìn)去，出來就是有序的：

const list = new SortedList([5, 1, 4, 2, 3]);

list.add(0);

console.log([...list]); // [0, 1, 2, 3, 4, 5]

console.log(list.at(2)); // 2

SortedSet 除了去重，還能做交并差集——類似兩個(gè)集合 a 和 b，a.intersection(b) 直接輸出 [3,4]，清晰得像在紙上學(xué)代數(shù)的樣子。SortedMap 用起來更像一張?jiān)趦?nèi)存里按 key 持久有序的報(bào)價(jià)表，irange(100,105) 把 price 從 100 到 105 之間的訂單按順序吐出來，一個(gè)區(qū)間查詢都不需要你再單獨(dú)過濾數(shù)組。

比較器這塊也沒含糊。對(duì) number 和 string 這兩種基本類型，庫(kù)默認(rèn)就有自然排序。當(dāng)你的 key 是自己定義的某種復(fù)雜對(duì)象時(shí)，TypeScript 會(huì)在編譯期強(qiáng)制你給出比較器，徹底杜絕以前那種悄悄把數(shù)字轉(zhuǎn)成字符串排序的傻事——這種 bug 是誰翻一次車記一輩子。

為什么不用紅黑樹？因?yàn)楝F(xiàn)代 CPU 吃連續(xù)內(nèi)存。底層設(shè)計(jì)是“分桶”。所有數(shù)據(jù)被分割到很多個(gè)小數(shù)組里，每個(gè)小數(shù)組自身保持有序，外面套一層記錄每個(gè)桶最大值的索引。定位到哪個(gè)桶用的是二分查找，實(shí)際插入或查詢的時(shí)候只動(dòng)那一個(gè)桶。這意味著大部分工作都在一小段連續(xù)的內(nèi)存上完成，CPU 的緩存得以用足。Python 的 sortedcontainers 賭的就是這一手，現(xiàn)在在 TypeScript 里同樣兌現(xiàn)了這個(gè)賭注。

這個(gè)結(jié)構(gòu)的另一個(gè)有趣之處體現(xiàn)在批量構(gòu)建上。構(gòu)造函數(shù)沒有傻傻地一個(gè)接一個(gè)插入元素，而是首先生成一份完整數(shù)組，直接排序，再按桶大小切片分配。于是，一次排完、一次切割搞定所有桶。拿性能數(shù)據(jù)來看，批量構(gòu)建跟逐個(gè)插入的對(duì)比是這樣的：SortedMap 在全量上都沒有劣勢(shì)，當(dāng)條目數(shù)達(dá)到 100 萬時(shí)，比單個(gè) add 快 3 倍。SortedSet 從大概 10 萬條開始拉開身位。SortedList 的情況最考驗(yàn)誠(chéng)實(shí)，百萬級(jí)數(shù)據(jù)里它贏得干脆，但在小、中規(guī)模時(shí)，逐個(gè)插入的路徑甚至比批量方式還快一點(diǎn)——所以如果你只處理幾千條數(shù)據(jù)，SortedList 的批量構(gòu)造未必是首選，但它也絕不會(huì)拖你后腿。

做這個(gè)庫(kù)的時(shí)候，最讓我上頭的其實(shí)不是算法本身，而是那種“明明 JavaScript 需要但一直沒人好好實(shí)現(xiàn)”的遺憾。