本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。

TIS-NET 第 20 關(guān)《超長(zhǎng)序列排序器》（Prolonged Sequence Sorter）關(guān)卡展示

本關(guān)會(huì)給你一個(gè)以 -1 結(jié)尾的超長(zhǎng)序列，序列中的數(shù)字都在 0~9 范圍內(nèi)。你需要將序列中的數(shù)字從小到大排好輸出給 OUT。

排序題我們?cè)谏弦徽碌?22 關(guān)做過(guò)，不過(guò)那一關(guān)的序列長(zhǎng)度短（不超過(guò) 10 個(gè)數(shù)字）、取值范圍大（10~99）。對(duì)于這樣的序列，我們總結(jié)出了規(guī)律，適合用選擇排序或插入排序算法。但是本關(guān)的數(shù)據(jù)正好反過(guò)來(lái)，取值范圍?。?~9），序列長(zhǎng)度長(zhǎng)（38 個(gè)數(shù)字）。如果仍然使用選擇排序或插入排序的話(huà)，我們的棧只有 15 格空間，是無(wú)法完成任務(wù)的。但是因?yàn)楸娟P(guān)數(shù)字的取值范圍小，我們可以使用計(jì)數(shù)排序來(lái)完成。

如果一個(gè)序列的取值范圍也大，序列長(zhǎng)度也長(zhǎng)的話(huà)，怎么排序呢？答案是：除非增加棧的數(shù)量，如果還是只有兩個(gè)棧，那么無(wú)解。

回顧一下計(jì)數(shù)排序的過(guò)程：

以下代碼假設(shè)提供的 nums 一定在 0~9 的范圍內(nèi)，并以 -1 結(jié)尾：

那么，我們現(xiàn)在根據(jù)示意圖和 C 語(yǔ)言代碼，寫(xiě)出本關(guān)的 TIS-100 代碼：

首先看右上角的節(jié)點(diǎn)：

1. 右上角的節(jié)點(diǎn)首先將上方棧里塞入 10 個(gè) 0，用于初始化 f 數(shù)組（mov 10 acc）

2. （mov 0 left）

3. （sub 1）

4. （jnz 2）

5. 然后進(jìn)入第一階段：每從上方收到一個(gè) num，我們都要將 f[num] 加上 1。由于 num 從 0 開(kāi)始，f[num] 是 f 數(shù)組的第 num+1 個(gè)元素，所以我們將數(shù)字 num 改寫(xiě)成 num+1（mov 1 acc）

6. （add up）

7. 并發(fā)給下方（mov acc down）。

8. 此時(shí)檢查：若 num+1 不為 0，說(shuō)明尚未到達(dá)?nums 數(shù)組最后的 -1，我們跳回第 5 行，繼續(xù)接收（jnz 5），直到到達(dá)最后的 -1 后，向下執(zhí)行，進(jìn)入第二階段。
   

現(xiàn)在暫時(shí)把目光移動(dòng)到中間靠右的節(jié)點(diǎn)處：

1. 中間靠右的節(jié)點(diǎn)是一個(gè)純傳話(huà)節(jié)點(diǎn)，第一階段里，它將收到的 num+1（mov up acc）

2. 發(fā)給左邊的節(jié)點(diǎn)，令其將 f[num] 加上 1（mov acc left）

3. （jnz 1）

4. 第二階段里，它將上方發(fā)來(lái)的所有數(shù)字全部無(wú)腦傳到右下角的節(jié)點(diǎn)里（mov up down）

5. （jmp 4）

中間靠左的節(jié)點(diǎn)用來(lái)維護(hù)頻數(shù)數(shù)組 f：

1. 它隨時(shí)等待右邊傳來(lái)?num+1（mov right acc）。

2. 如果 num+1 為 0，即 num 為 -1，則跳回第 1 行，什么都不做（jez 1）。

3. 接下來(lái)的代碼就是將 f 數(shù)組的第 num+1 個(gè)元素 f[num] 加上 1，和之前《眾數(shù)》題里的代碼大同小異（傳送門(mén)：【TIS-100 攻略】TIS-NET 第 10 關(guān)：序列眾數(shù)計(jì)算器）。這里就長(zhǎng)話(huà)短說(shuō)了：上方彈棧 num+1 次后（sav）

4. （mov up down）

5. （sub 1）

6. （jnz 4）

7. 下方棧頂里的數(shù)字即為 f[num]，將其（mov down acc）

8. 加上 1 后（add 1）

9. 放回原處（mov acc down）。

10. 處理完成后，下方往回彈棧 num+1 次（swp）

11. （mov down up）

12. （sub 1）

13. （jnz b）

以上便是第一階段的全部工作?，F(xiàn)在進(jìn)入第二階段，我們將目光回到上方節(jié)點(diǎn)。第一階段里，上方節(jié)點(diǎn)的 acc 用來(lái)存儲(chǔ) num+1 的值，到了第二階段，acc 就要改為存儲(chǔ) num 了。進(jìn)入第二階段的條件是 num+1 = 0，所以進(jìn)入第二階段后，上方節(jié)點(diǎn)的 acc 一定是 0，正好是第一個(gè) num 的值。接下來(lái)：

9. 上方節(jié)點(diǎn)將每個(gè) num（mov acc down）

10. 以及對(duì)應(yīng)的 f[num] 都發(fā)到中間靠右的節(jié)點(diǎn)里（mov left down），

11. 然后判斷：如果 num 到達(dá)了 9（sub 9），

12. 則跳到第 15 行執(zhí)行（jez f），

13. 否則令 num 加 1（add 10），

14. 并跳回第 9 行繼續(xù)發(fā)送下一組 num 和 f[num]（jmp 9）。

15. 直到 num 到達(dá) 9 后，向下發(fā)送最終的 -1（mov -1 down）。

中間靠右的節(jié)點(diǎn)將每一組 num 和對(duì)應(yīng)的 f[num] 都發(fā)到右下角的輸出節(jié)點(diǎn)里（mov up down, jmp 4）。最后是右下角的輸出節(jié)點(diǎn)：

1. 右下角的節(jié)點(diǎn)收到 num 后（mov up acc），檢查是否是負(fù)數(shù)。

2. 是負(fù)數(shù)時(shí)，說(shuō)明收到了 -1，直接跳到第 7 行輸出這個(gè) -1（jlz 7, mov acc down）。

3. 若不是負(fù)數(shù)，則說(shuō)明接下來(lái)還會(huì)收到對(duì)應(yīng)的 f[num]。我們將 num 暫時(shí)存入 bak（swp），

4. 然后從上方接收 f[num]（mov up acc）。

5. f[num] 為 0 時(shí)，表示序列中沒(méi)有出現(xiàn)過(guò)當(dāng)前的 num，直接跳回第 1 行接收下一組數(shù)據(jù)（jez 1）；

6. f[num] 不為 0 時(shí)，每輸出一個(gè) num（swp）

7. （mov acc down）

8. （swp）

9. 就將 f[num] 減去 1（sub 1）。

10. 只要 f[num] 沒(méi)有減到 0，就跳回第 6 行繼續(xù)輸出 num（jnz 6），直到 f[num] 減到 0 后，跳回第 1 行，接收下一組數(shù)據(jù)。

點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：